题目

P3857 [TJOI2008]彩灯

分析

线性基模板题。

直接构造线性基，然后可以构造的集合个数就是 \(2^n\) 。

代码

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
	x=0;char ch=getchar();bool f=false;
	while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return ;
}
template <typename T>
inline void write(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
	return ;
}
const int MN=52;
#define ll long long
ll n,m,cnt,a[MN],tmp[MN]; 
char str[MN];
bool flag=false;
void insert(ll x){
	for(int i=MN;~i;i--){
		if(x&(1ll<<i)){
			if(!a[i]){a[i]=x;return ;}
			else x^=a[i];
		}
	}
	flag=true;
	return ;
}
bool check(ll x){
	for(int i=MN;~i;i--){
		if(x&(1ll<<i)){
			if(!a[i]) return false;
			else x^=a[i];
		}
	}
	return true;
}
ll QueryMax(ll x=0){
	for(int i=MN;~i;i--) x=max(x,x^a[i]);
	return x;
}
ll QueryMin(){
	if(flag) return 0;
	for(int i=0;i<=MN;i++) if(a[i]) return a[i];
}
ll Query(ll k){
    ll res=0;int cnt=0;
    k-=flag;if(!k)return 0;
    for(int i=0;i<=MN;i++){
        for(int j=i-1;~j;j--) if(a[i]&(1ll<<j))a[i]^=a[j];
        if(a[i]) tmp[cnt++]=a[i];
    }
    if(k>=(1ll<<cnt))return -1;
    for(int i=0;i<cnt;i++)if(k&(1ll<<i))res^=tmp[i];
    return res;
}
int main(){
	read(n),read(m);ll x=0;
	for(int i=1;i<=m;i++){
		scanf("%s",str);x=0;
		for(int j=0;j<n;j++) if(str[j]=='O') x|=(1ll<<j); 
		insert(x);
	}
	int cnt=0;
	for(int i=0;i<=MN;i++) if(a[i]) cnt++; 
	write((1ll<<cnt)%2008);
	return 0;
}