洛谷P3857 [TJOI2008]彩灯(线性基)

题目描述

Peter女朋友的生日快到了，他亲自设计了一组彩灯，想给女朋友一个惊喜。已知一组彩灯是由一排N个独立的灯泡构成的，并且有M个开关控制它们。从数学的角度看，这一排彩灯的任何一个彩灯只有亮与不亮两个状态，所以共有2N个样式。由于技术上的问题，Peter设计的每个开关控制的彩灯没有什么规律，当一个开关被按下的时候，它会把所有它控制的彩灯改变状态（即亮变成不亮，不亮变成亮）。假如告诉你他设计的每个开关所控制的彩灯范围，你能否帮他计算出这些彩灯有多少种样式可以展示给他的女朋友？

注： 开始时所有彩灯都是不亮的状态。

输入输出格式

输入格式：

 

每组测试数据第一行为两个整数N和M，用空格隔开。紧接着是有M行，每行都是一个长度为N的字符串，表示一个开关控制彩灯的范围（N盏灯），如果第i个字母是大写字母’O’，则表示这个开关控制第i盏灯，如果第i个字母是大写字母’X’，则表示这个开关不控制此灯。

 

输出格式：

 

输出这些开关和彩灯可以变换出来的样式数目。由于这个值可能会很大，请求出它对于整数2008的余数。

 

输入输出样例

输入样例#1： 复制

2 3
OO
XO
OX

输出样例#1： 复制

4

说明

可见样例中第一个开关控制了所有的彩灯，而后两个开关分别控制了第一个和第二个彩灯，这样我们可以只用后两个开关控制彩灯，可以变换出来所有的22个状态。

30%的数据中，N和M不超过15。

70%的数据中，N和M不超过50。

 

要是不知道这题是线性基的话可能要想很久，。。

但是知道了线性基这题就比较zz了，就是求个最大线性无关组，直接输出pow(2,线性基的大小)

 

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long 
using namespace std;
const int MAXN = 1e5 + 10,  B = 62, mod = 2008;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M;
char s[MAXN];
LL P[MAXN];
void Insert(LL x) {
    for(int i = B; i >= 0; i--) {
        if((x >> i) & 1) {
            if(!P[i]) {P[i] = x; return ;}
            x = x ^ P[i];
        }
    }
}
main() { 
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    scanf("%d %d", &N, &M);
    for(int i = 1; i <= M; i++) {
        scanf("%s", s + 1);
        LL now = 0;
        for(int j = 1; j <= N; j++) 
            if(s[j] == 'X') 
                now = now | (1ll << j - 1);
    //    printf("%d\n", now);
        Insert(now);
    }
    int num = 0;
    for(int i = 0; i <= B; i++) 
        if(P[i]) num++;
    printf("%lld", (1ll << num) % mod );
}