正题
题目链接:https://www.luogu.com.cn/problem/P3857
题目大意
n
n
n个彩灯，
m
m
m个开关能使得某些彩灯取反，求有多少种彩灯样式。
解题思路
其实就是
m
m
m个数种若干个数异或起来有多少不同的数。
又是一道考线性基性质的题目，因为线性基中任何一个数不为其他数的异或和。也就是在线性基中我们选出若干个数异或起来，选择方案不同结果必然不同。
所以
s
i
z
siz
siz表示线性基大小的话，答案就是
2
s
i
z
2^{siz}
2siz
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std
;
const ll N
=80;
ll n
,m
,ans
,d
[N
];
char s
[N
];
void add(ll x
){
for(ll i
=n
;i
>=0;i
--)
if((x
>>i
)&1){
if(d
[i
])x
^=d
[i
];
else{
ans
++;
d
[i
]=x
;
break;
}
}
return;
}
int main()
{
scanf("%lld%lld",&n
,&m
);
for(ll i
=1;i
<=m
;i
++){
ll x
=0;scanf("%s",s
);
for(ll j
=0;j
<n
;j
++)
x
|=(s
[j
]=='O')*(1ll<<j
);
add(x
);
}
printf("%lld",(1ll<<ans
)%2008);
}
