題目描述

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

注： 開始時所有彩燈都是不亮的狀態。

輸入輸出格式

輸入格式：

每組測試數據第一行為兩個整數N和M，用空格隔開。緊接著是有M行，每行都是一個長度為N的字符串，表示一個開關控制彩燈的范圍（N盞燈），如果第i個字母是大寫字母’O’，則表示這個開關控制第i盞燈，如果第i個字母是大寫字母’X’，則表示這個開關不控制此燈。

輸出格式：

輸出這些開關和彩燈可以變換出來的樣式數目。由于這個值可能會很大，請求出它對于整數2008的余數。

輸入輸出樣例

輸入樣例#1：

2 3
OO
XO
OX

輸出樣例#1：

4

說明/提示

可見樣例中第一個開關控制了所有的彩燈，而后兩個開關分別控制了第一個和第二個彩燈，這樣我們可以只用后兩個開關控制彩燈，可以變換出來所有的2*2個狀態。

30%的數據中，N和M不超過15。

另外有40%的數據中，N和M有一個為50

100%的數據中，N和M不超過50。

思路：

對于每個開關，可以看成一個 01 串，初始是一個全部為 0 的串，要求經過這些開關的操作后，出現的不同的 01 串的個數

由于異或具有相消性，開關符合異或的特性，考慮到最終要求不同的串的個數，可利用線性基來解決

在線性基中，其中的元素是不重復的，因此可以將這些 01 串轉為 10 進制后存入線性基，然后統計線性基中元素的個數 res

線性基中的元素均是由外界元素異或出來的，因此，對于線性基中的每個元素，都有選、不選兩種情況，故而最終答案為 (1<<res)%2008

源代碼

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> const int MOD = 2008; const int N = 1000+5; const int dx[] = {0,0,-1,1,-1,-1,1,1}; const int dy[] = {-1,1,0,0,-1,1,-1,1}; using namespace std;LL res; struct LinearBasis {LL d[60+5];//線性基LinearBasis() {memset(d,0,sizeof(d));}bool add(LL x){for(int i=60; i>=0; i--){if(x&(1LL<<i)) {if(d[i])//插入失敗，異或x^=d[i];else {//插入成功，保存后退出res++;//記錄插入成功的個數d[i]=x;break;}}}return x>0;//x>0插入成功} }lb; int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){char str[100];scanf("%s",str);LL x=0;for(int i=0;i<strlen(str);i++)//將字符串轉成數if(str[i]=='O')x+=(1LL<<(n-i));lb.add(x);//加入線性基}printf("%lld\n",(1LL<<res)%2008);return 0; }

總結

以上是生活随笔為你收集整理的彩灯（洛谷-P3857）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。