彩灯
题目描述
Peter女朋友的生日快到了，他亲自设计了一组彩灯，想给女朋友一个惊喜。已知一组彩灯是由一排N个独立的灯泡构成的，并且有M个开关控制它们。从数学的角度看，这一排彩灯的任何一个彩灯只有亮与不亮两个状态，所以共有2N个样式。由于技术上的问题，Peter设计的每个开关控制的彩灯没有什么规律，当一个开关被按下的时候，它会把所有它控制的彩灯改变状态（即亮变成不亮，不亮变成亮）。假如告诉你他设计的每个开关所控制的彩灯范围，你能否帮他计算出这些彩灯有多少种样式可以展示给他的女朋友？
注： 开始时所有彩灯都是不亮的状态。
输入输出格式
输入格式：
每组测试数据第一行为两个整数N和M，用空格隔开。紧接着是有M行，每行都是一个长度为N的字符串，表示一个开关控制彩灯的范围（N盏灯），如果第i个字母是大写字母’O’，则表示这个开关控制第i盏灯，如果第i个字母是大写字母’X’，则表示这个开关不控制此灯。
输出格式：
输出这些开关和彩灯可以变换出来的样式数目。由于这个值可能会很大，请求出它对于整数2008的余数。
输入输出样例
说明
可见样例中第一个开关控制了所有的彩灯，而后两个开关分别控制了第一个和第二个彩灯，这样我们可以只用后两个开关控制彩灯，可以变换出来所有的22个状态。
30%的数据中，N和M不超过15。
70%的数据中，N和M不超过50。
分析：
很显然，控制器可以转换成一个二进制数，那么很不难想到用线性基了。
但是这道题有个坑点，因为控制器控制的位置要么都亮要么都不亮，所以是不能分开控制的，那么求出线性基以后当然不能简单的异或，应该是每有一个基向量就让答案乘以2再加1。还有一种全部灯都不亮的情况，所以最后答案还要加1。（做出来这题后被读入卡了好久。。。）
Code：
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,m,a[51],b[71],ans; int main() { scanf("%lld%lld",&n,&m); char ch[71]; for(int i=1;i<=m;i++){ scanf("%s",ch); for(int j=0;j<n;j++) if(ch[j]=='O') a[i]^=(1LL<<j);} for(int i=1;i<=m;i++) for(int j=62;j>=0;j--){ if(!(a[i]>>j))continue; if(!b[j]){b[j]=a[i];break;} a[i]^=b[j];} for(int j=62;j>=0;j--) if(b[j])ans=ans*2+1;ans++; printf("%lld",ans%2008); return 0; }