HDU 4810 Wall Painting(異或 +按位容斥)
來源：程序員人生 發布時間：2014-12-13 08:39:21 閱讀次數：2428次
直接不會，預估時間復雜度，對C（n,m） 到范圍為500就瞎了。當時也想算法應當接近常數級別的。
如果真的算必定跪。回頭看了下解題報告。
話說比賽很喜歡考異或，“位”思想，組合問題
對計算選取k個數字時候，分別計算各個位上可能出現的情況，然后計算各個位上的累加和。即使1個數字可由很多位組成但是每次計算1個位
記錄每位上１的個數（這里只需要３２位），對第i天，必須要選出奇數個１才能使該位異或結果位１，否則為０。我們來看樣例，
4
1 2 10 1
這４個數的2進制表示分別為：
0001
0010
1010
0001
比如第２天的時候, 從４個當選出２個來做異或，第４位上只有１個１，所以有３當選法可使得這1位異或以后結果為１，（也就是Ｃ(3,1) * C(1,1))，第３位的沒有１，所以異或結果1定為０，第２位上又２個１，所以有４種選法，同理第1位上也是４種。
所以其結果就是 (1<<3)*C(3,1) + 0 * C(4,2) + (1<<1)*C(2,1)*C(2,1) + (1<<0)*C(2,1)*C(2,1)
注意細節：1.預處理C數組，注意范圍，1個位上種類的選取是奇數但不能超過可選的數字。特別容易溢出。都用 long long
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define inf 0x3f3f3f3f
#define maxn 1100
#define MOD 1000003
using namespace std;
int N;
long long rem[32],c[maxn][maxn];
void init() {
c[0][0] = c[1][0] = c[1][1] = 1;
for (int i = 2; i < maxn; i++) {
c[i][0] = 1;
for (int j = 1; j <= i; j++)
c[i][j] = (c[i⑴][j] + c[i⑴][j⑴]) % MOD;
}
return ;
}
int main()
{init();
while(~scanf("%d",&N)){
memset(rem,0,sizeof(rem));
for(int i=0;i<N;i++){
int k;scanf("%d",&k);
for(int j=0;j<32;j++)
if( (1<<j)& k ) rem[j]++;
}
for(int i=1;i<=N;i++){
long long ans=0;
for(int j=0;j<32;j++){
for(int k=1;k<=rem[j] && k<=i;k+=2)
ans=(ans+ ( c[N-rem[j]][i-k]* (c[rem[j]][k]* ( (1<<j)%MOD) )%MOD)%MOD)%MOD;
}
if(i==N) printf("%I64d
",ans);
else printf("%I64d ",ans);
}
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
