显然是一个线性基的问题,那么很显然要用线性基
想要知道所有的方案数,线性基的性质就是用其中的元素\(xor\) 出来的元素保证互不相等
这样的话只要知道线性基内元素的数量就可以了
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<class T>inline void read(T &x)
{
x=0;register char c=getchar();register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=-x;
}
template<class T>inline void print(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar('0'+x%10);
}
string s;
int p[60];
int n,m;
int cnt;
int num;
void add(int x){
for(int i=n-1;i>=0;--i){
if(((1ll<<i)&x)==0) continue;
if(!p[i]){
cnt++;
p[i]^=x;
break;
}
x^=p[i];
}
}
signed main(){
read(n);read(m);
for(int i=1;i<=m;++i){
cin>>s;
num=0;
for(int j=n-1;j>=0;--j){
if(s[j]=='O'){
num|=(1ll<<j);
}
}
add(num);
}
cout<<(1ll<<cnt)%2008;
return 0;
}