http://www.lydsy.com/JudgeOnline/problem.php?id=2844

線性基。。。

先把線性基搞出來，然后不斷逼近答案，如果這個(gè)基比答案小了，那么說明要加上，同時(shí)加上貢獻(xiàn)：現(xiàn)在的位i +1<<(now-i) 為什么呢，我是這樣理解的：一個(gè)數(shù)分兩種情況：選這位和不選這位，如果前面選的位和當(dāng)前q不同的話，那么前面已經(jīng)統(tǒng)計(jì)過答案了，每次統(tǒng)計(jì)答案都是當(dāng)已經(jīng)選的數(shù)是q的一個(gè)子集。我們統(tǒng)計(jì)的答案是不選這個(gè)位，不選的話，肯定q小，那么這樣的數(shù)有1<<(now-i)個(gè)，因?yàn)楹竺嬗衝ow-i個(gè)基。

然后還要+1，因?yàn)槲覀冎唤y(tǒng)計(jì)了比這個(gè)數(shù)小的數(shù)的個(gè)數(shù)。還要乘上2^(n-now)，因?yàn)榍懊鎛ow個(gè)數(shù)已經(jīng)足夠構(gòu)成基底，那么后面n-now個(gè)數(shù)肯定會重復(fù)。這樣會復(fù)制2^(n-now)個(gè)數(shù)。

還有一種解釋方法：因?yàn)楹竺娑急幌?了，所以選不選都沒關(guān)系，又因?yàn)楹竺婷總€(gè)a的組合都不一樣，和前面搭配都不一樣，所以可以。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 100010, mod = 10086; int n, now; ll q; ll a[N], bin[40]; void gauss() {now = 1;for(int i = 30; i >= 0; --i){int x = now;while(x <= n && !(a[x] & bin[i])) ++x; //沒有這位if(x == n + 1) continue;swap(a[now], a[x]); // 消去這位其他的1for(int j = 1; j <= n; ++j) if(j != now && a[j] & bin[i]) a[j] ^= a[now]; ++now;}--now; } int main() {bin[0] = 1; for(int i = 1; i <= 30; ++i) bin[i] = bin[i - 1] * 2;scanf("%d", &n);for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);scanf("%d", &q);gauss();ll ans = 0, val = 0;for(int i = 1; i <= now; ++i) if((val ^ a[i]) <= q) {val ^= a[i];ans += bin[now - i] % mod;}for(int i = 1; i <= n - now; ++i) ans = (ans << 1) % mod;++ans;printf("%lld\n", (ans % mod + mod) % mod); return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/19992147orz/p/6836092.html

總結(jié)

以上是生活随笔為你收集整理的bzoj2844的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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