洛谷P3857 [TJOI2008]彩灯 [线性基]

时间:2024-01-03 09:16:02

  题目传送门

彩灯

题目描述

Peter女朋友的生日快到了,他亲自设计了一组彩灯,想给女朋友一个惊喜。已知一组彩灯是由一排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。


  分析:

  很显然,控制器可以转换成一个二进制数,那么很不难想到用线性基了。

  但是这道题有个坑点,因为控制器控制的位置要么都亮要么都不亮,所以是不能分开控制的,那么求出线性基以后当然不能简单的异或,应该是每有一个基向量就让答案乘以2再加1。还有一种全部灯都不亮的情况,所以最后答案还要加1。(做出来这题后被读入卡了好久。。。)

  Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,a[],b[],ans;
int main()
{
scanf("%lld%lld",&n,&m);
char ch[];
for(int i=;i<=m;i++){
scanf("%s",ch);
for(int j=;j<n;j++)
if(ch[j]=='O')
a[i]^=(1LL<<j);}
for(int i=;i<=m;i++)
for(int j=;j>=;j--){
if(!(a[i]>>j))continue;
if(!b[j]){b[j]=a[i];break;}
a[i]^=b[j];}
for(int j=;j>=;j--)
if(b[j])ans=ans*+;ans++;
printf("%lld",ans%);
return ;
}