文章目录

• • • • R e s u l t Result Result
      • H y p e r l i n k Hyperlink Hyperlink
      • D e s c r i p t i o n Description Description
      • S o l u t i o n Solution Solution
      • C o d e Code Code

R e s u l t Result Result

---

H y p e r l i n k Hyperlink Hyperlink

https://www.luogu.com.cn/problem/P3857

---

D e s c r i p t i o n Description Description

有 n n n种开关灯方式（形如改变/不改变某盏灯的状态），你可以选择进行其中的若干种，问最终可能的开关灯形态，答案对2008取模

数据范围： l e n , n ≤ 50 len,n\leq 50 len,n≤50

---

S o l u t i o n Solution Solution

我们把控制某盏灯看做是二进制下的1，因为我们控制一盏灯偶数次相当于没控制，这类似于异或

考虑线性基，将这 n n n种开关灯方式状压，然后扔进线性基里，最后 2 线 性 基 的 大 小 2^{线性基的大小} 2线性基的大小即为答案

时间复杂度： O ( n × l e n ) O(n\times len) O(n×len)

---

C o d e Code Code

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;int n,len,tot;
LL a[61],x;
char s[51];
bool flg;
inline LL read()
{
	char c;LL d=1,f=0;
	while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;
	while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;
	return d*f;
}
inline void Insert(LL x)
{
	for(register int i=60;~i;i--) if((x>>i)&1) if(a[i]==0){a[i]=x;tot++;return;}else x^=a[i];
	return (void)(flg=true);
}
signed main()
{
	len=read();n=read();
	for(register int i=1;i<=n;i++)
	{
		scanf("%s",s+1);x=0;
		for(register int j=1;j<=len;j++) x=(x<<1)+(s[j]=='O');
		Insert(x);
	}
	printf("%lld",(1ll<<tot)%2008);
}