題目：

Peter 女朋友的生日快到了，他親自設(shè)計(jì)了一組彩燈，想給女朋友一個(gè)驚喜。已知一組彩燈是由一排 N個(gè)獨(dú)立的燈泡構(gòu)成的，并且有 MM 個(gè)開關(guān)控制它們。從數(shù)學(xué)的角度看，這一排彩燈的任何一個(gè)彩燈只有亮與不亮兩個(gè)狀態(tài)，所以共有 2^N個(gè)樣式。由于技術(shù)上的問題，Peter 設(shè)計(jì)的每個(gè)開關(guān)控制的彩燈沒有什么規(guī)律，當(dāng)一個(gè)開關(guān)被按下的時(shí)候，它會(huì)把所有它控制的彩燈改變狀態(tài)（即亮變成不亮，不亮變成亮）。假如告訴你他設(shè)計(jì)的每個(gè)開關(guān)所控制的彩燈范圍，你能否幫他計(jì)算出這些彩燈有多少種樣式可以展示給他的女朋友？

注： 開始時(shí)所有彩燈都是不亮的狀態(tài)。

題解：

線性基裸題，把n個(gè)數(shù)插入線性基，ans=(1<<線性基大小)%2008

代碼：

#include<bits/stdc++.h> #define lol long long using namespace std; const int N=51,mod=2008; int cnt; lol arr[N]; void init (lol box) {for(int i=50;i>=0;i--) {if(!(box>>i&1)) continue; if(!arr[i]) {++cnt,arr[i]=box;break;}else box^=arr[i];} } int main() {int n,m; scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) {char s[N]; scanf("%s",s);int len=strlen(s); lol x=0;for(int i=0;i<len;i++) x+=(1ll<<(n-i))*(s[i]=='O');init(x);}printf("%lld\n",(1ll<<cnt)%mod);return 0; }

總結(jié)

以上是生活随笔為你收集整理的[TJOI2008]彩灯的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。