题解 P3857 【[TJOI2008]彩灯】

一个线性基的板子，蒟蒻刚学线性基，无意看见了这道题

其实线性基就是一个贪心，每次匹配最高位，如果最高位为1，那就匹配成功，为0,就匹配失败，线性基有许多一些好玩的性质，

1.线性基的异或集合中每个元素的异或方案唯一，

2.线性基二进制最高位互不相同。

3.如果线性基是满的，它的异或集合为[1,2n−1]。

4.线性基中元素互相异或，异或集合不变。

所以其实这题就是把O和X看做二进制的0和1，改变状态即异或，每一行看做一个数字。

然后因为是求方案数，那么就是求线性基中的数字个数就可以啦

代码:

#include<bits/stdc++.h>
#define int long long//偷懒的好方法
long long n,x,j,ans,m,a[5000005];//数组好像不用这么大来着
signed main(){
  scanf("%lld%lld",&n,&m);
  for (int i=1;i<=m;i++){
    char s[10005];
    scanf("%s",s);//S是读入的字符串
    int len=strlen(s);
    int x=0;
    for (int i=0;i<len;i++) if (s[i]=='O')  x+=(1ll<<(n-i));//转二进制为整数
    for (int j=62;j>=0;j--){
      if ((x>>j)==0) continue;
      if (a[j]==0){
        a[j]=x;
        break;//如果已经能被其他数字异或求出了，那直接break
      }
      x^=a[j];
    }//线性基的匹配
  }
  long long ans=0;
  for (int i=62;i>=0;i--) if (a[i]) ans++;//统计线性基中的数字个数
  printf("%lld",(1ll<<ans)%2008);//b别忘了取模，在右移的时候要把1定为long long
}