G63 线性基 异或和的方案数 P3857 [TJOI2008] 彩灯

视频链接：G63 线性基 异或和的方案数 P3857 [TJOI2008] 彩灯_哔哩哔哩_bilibili

P3857 [TJOI2008] 彩灯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// 线性基 O(55*n)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define LL long long
const int N=60,mod=2008;
int n,m,k;
LL a[N];

void gauss(){
  for(int i=55;i>=0;i--){
    for(int j=k;j<m;j++)
      if(a[j]>>i&1){swap(a[j],a[k]); break;}
    if((a[k]>>i&1)==0) continue;
    for(int j=0;j<m;j++)
      if(j!=k&&(a[j]>>i&1)) a[j]^=a[k];
    k++; if(k==m) break;
  }
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=0;i<m;i++){
    char s[N]; scanf("%s",s);
    LL x=0;
    for(int j=0;j<strlen(s);j++)
      x+=(1ll<<(n-j))*(s[j]=='O');
    a[i]=x;
  }
  gauss();
  printf("%lld\n",(1ll<<k)%mod);
}