洛谷3857 [TJOI2008]彩灯

题目描述

已知一组彩灯是由一排N个独立的灯泡构成的，并且有M个开关控制它们。从数学的角度看，这一排彩灯的任何一个彩灯只有亮与不亮两个状态，所以共有2N个样式。由于技术上的问题，Peter设计的每个开关控制的彩灯没有什么规律，当一个开关被按下的时候，它会把所有它控制的彩灯改变状态（即亮变成不亮，不亮变成亮）。假如告诉你他设计的每个开关所控制的彩灯范围，你能否帮他计算出这些彩灯有多少种样式可以展示给他的女朋友？

注： 开始时所有彩灯都是不亮的状态。

输入输出格式

输入格式：

每组测试数据第一行为两个整数N和M，用空格隔开。紧接着是有M行，每行都是一个长度为N的字符串，表示一个开关控制彩灯的范围（N盏灯），如果第i个字母是大写字母’O’，则表示这个开关控制第i盏灯，如果第i个字母是大写字母’X’，则表示这个开关不控制此灯。

输出格式：

输出这些开关和彩灯可以变换出来的样式数目。由于这个值可能会很大，请求出它对于整数2008的余数。

输入输出样例

输入样例#1：
2 3 OO XO OX 输出样例#1：
4

说明

可见样例中第一个开关控制了所有的彩灯，而后两个开关分别控制了第一个和第二个彩灯，这样我们可以只用后两个开关控制彩灯，可以变换出来所有的22个状态。

30%的数据中，N和M不超过15。

70%的数据中，N和M不超过50。

 

本题可以翻译成给出M个N位二进制数 ， 取若干个异或，求有多少种结果。

本质就是求出线性基的个数x，结果即为2^x

线性基就是把原有的集合用一个新的集合替代之，新的集合里面数相互异或可以得出原有集合的数相互异或的答案。

搞出线性基的性质 : a 和 b 的所有xor 结果 等同于 a和 a xor b的所有结果

代码

#include<bits/stdc++.h> using namespace std; int N,M,cnt,ans; long long P[128]; char s[128]; void insert(long long x) {for(int i=62;i>=0;i--)if((x>>i)&1){if(!P[i]){P[i]=x;break;}else x^=P[i];} } int main() {scanf("%d%d",&N,&M);for(int i=1;i<=M;i++){scanf("%s",s);long long a=0;for(int j=0;j<N;j++)if(s[j]=='O')a^=(1ll<<j);insert(a);}for(int i=0;i<=62;i++)if(P[i])ans++;printf("%lld",(1ll<<ans)%2008);return 0; }

 

转载于:https://www.cnblogs.com/Elfish/p/7649059.html

总结

以上是生活随笔为你收集整理的洛谷3857 [TJOI2008]彩灯的全部内容，希望文章能够帮你解决所遇到的问题。

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