zcmimi's blog
查看原题

点击跳转

线性基中每个元素的异或方案唯一,也就是说,线性基中不同的异或组合异或出的数都是不一样的。

那么我们把字符串转成二进制,然后插入线性基

线性基内的元素都是由外界元素异或出来的,那么对于线性基内每个元素,我们都有选/不选两种情况,

假设线性基内有cnt个元素,答案就是2^{cnt}

#include<cstdio>
typedef long long ll;
int n,m,ans;
ll p[51];
char s[50];
void ins(ll x){
    for(int i=n;x,~i;--i)if(x>>i){
        if(!p[i]){
            p[i]=x,++ans;
            return;
        }
        x^=p[i];
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%s",s);
        ll x=0;
        for(int j=0;j<n;++j)
            if(s[j]=='O')x+=1<<n-j;
        ins(x);
    }
    printf("%d\n",(1ll<<ans)%2008);
}
LG 3857 [TJOI2008]彩灯
comment评论
Search
search