彩燈

luogu 3857

金牌導(dǎo)航 線性基-1

題目大意

給若干個01串，讓你選擇其中一些，問你異或的值有多少種

輸入樣例

2 3 OO XO OX

輸出樣例

4

數(shù)據(jù)范圍

$1?N,M?50$

解題思路

對于原來的01串，先求出其線性基（大小為k）
根據(jù)集合中的任何數(shù)能且只能由線性基中的一種組合異或而得
結(jié)果就是$2^k$

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define wyc 2008 using namespace std; ll n, m, ans, d[60]; string str; int main() {scanf("%lld%lld", &n, &m);ans = 1;for (ll i = 1; i <= m; ++i){cin>>str;ll x = 0;for (int j = 0; j < n; ++j)x = x * 2 + (str[j] == 'O'? 1: 0);for (int j = 50; j >= 0; --j)if (x & (1ll<<j))//求線性基{if (d[j]) x ^= d[j];else{d[j] = x;ans = ans * 2 % wyc;//計算結(jié)果break;}}}printf("%lld", ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【线性基】彩灯（luogu 3857/金牌导航 线性基-1）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。