洛谷P3857 [TJOI2008]彩灯(线性基)
程序员文章站
2022-07-10 20:12:47
题目描述 Peter女朋友的生日快到了,他亲自设计了一组彩灯,想给女朋友一个惊喜。已知一组彩灯是由一排N个独立的灯泡构成的,并且有M个开关控制它们。从数学的角度看,这一排彩灯的任何一个彩灯只有亮与不亮两个状态,所以共有2N个样式。由于技术上的问题,Peter设计的每个开关控制的彩灯没有什么规律,当一 ......
题目描述
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。
要是不知道这题是线性基的话可能要想很久,。。
但是知道了线性基这题就比较zz了,就是求个最大线性无关组,直接输出pow(2,线性基的大小)
// luogu-judger-enable-o2 #include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; const int MAXN = 1e5 + 10, B = 62, mod = 2008; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M; char s[MAXN]; LL P[MAXN]; void Insert(LL x) { for(int i = B; i >= 0; i--) { if((x >> i) & 1) { if(!P[i]) {P[i] = x; return ;} x = x ^ P[i]; } } } main() { #ifdef WIN32 freopen("a.in", "r", stdin); #endif scanf("%d %d", &N, &M); for(int i = 1; i <= M; i++) { scanf("%s", s + 1); LL now = 0; for(int j = 1; j <= N; j++) if(s[j] == 'X') now = now | (1ll << j - 1); // printf("%d\n", now); Insert(now); } int num = 0; for(int i = 0; i <= B; i++) if(P[i]) num++; printf("%lld", (1ll << num) % mod ); }