首页 > 其他 > 详细

Luogu P3857 [TJOI2008]彩灯

时间:2020-05-01 12:49:51      阅读:64      评论:0      收藏:0      [点我收藏+]

把每个对应的序列看成二进制数,能控制就把这一位设为\(1\),那么每异或出来一个新的数就对应一种情况。
根据线性基的性质,任意一个子集异或和都不一样,所以直接线性基即可。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define R register
#define LL long long

const int Mod=2008;

int n,m;
char s[70];
LL p[70];
int cnt;
LL a[70];

inline void ins(LL x) {
	for(R int i=62;i>=0;i--)
		if(x&(1LL<<i)) {
			if(!p[i]) { p[i]=x,cnt++; break; }
			else x^=p[i];
		}
}

int main() {
//	freopen("a.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(R int i=1;i<=m;i++) {
		scanf("%s",s);
		for(R int j=0;j<n;j++)
			if(s[j]==‘O‘) a[i]|=(1LL<<j);
	}
	for(R int i=1;i<=m;i++) ins(a[i]);
	int ans=1;// printf("%d\n",cnt);
	while(cnt--) ans*=2,ans%=Mod;
	printf("%d\n",ans);
	return 0;
}

Luogu P3857 [TJOI2008]彩灯

原文:https://www.cnblogs.com/HN-wrp/p/12812964.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!