彩灯（洛谷-P3857）

题目描述

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）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。