題意：
? ? ?給你n個(gè)數(shù)，讓你輸出n個(gè)數(shù)，沒一次輸出的是在這n個(gè)數(shù)里面取i個(gè)數(shù)異或的和（所有情況<C n中取i>）。

思路：
? ? ?首先把所有的數(shù)都拆成二進(jìn)制，然后把他們?cè)谀骋晃簧系臄?shù)字加起來(lái)，比如 ? ? ? ?3 = 11 ?5 = 101 他倆合并就是 112 就這樣吧所有的數(shù)都合并了，一共最多32位，然后我們考慮，對(duì)于每一位，只有選擇奇數(shù)個(gè)1的時(shí)候才會(huì)是1，否則就是0 ，所以我們可以一次枚舉每一位，比如當(dāng)前要取6個(gè)數(shù)，對(duì)于第三位有8個(gè)1，那么當(dāng)前的這位就是
? ? ?C[8][1] * C[N-8][6-1] * 2^3?
? + C[8][3] * C[N-8][6-3] * 2^3?
? + C[8][5] * C[N-8][6-5] * 2^3

其中變化的那個(gè)1 3 5 就是去奇數(shù)的情況，每一次取完奇數(shù)后乘以剩下的的（6 - 奇數(shù)）的情況就是一共有多上中取當(dāng)前奇數(shù)的情況 然后在乘以對(duì)應(yīng)位上產(chǎn)生的數(shù) 2^3加在一起就是當(dāng)要求取6個(gè)的時(shí)候在第三位上的8個(gè)1能產(chǎn)生的價(jià)值。

#include<stdio.h> #include<string.h>#define N 1005 __int64 C[N][N]; __int64 A[40] ,B[40]; __int64 mod = 1000003;void DB_C() {C[0][0] = C[1][0] = C[1][1] = B[1] = 1;for(int i = 2 ;i <= 35 ;i ++)B[i] = B[i-1] * 2 % mod;for(int i = 2 ;i <= 1002 ;i ++){C[i][0] = 1;for(int j = 1 ;j <= i ;j ++)C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;}return ; }int main () {int n ,i ,j ,k ,num;DB_C();while(~scanf("%d" ,&n)){memset(A ,0 ,sizeof(A));for(i = 1 ;i <= n ;i ++){scanf("%d" ,&num);int tt = 0;while(num){A[++tt] += (num&1);num /= 2;}}for(i = 1 ;i <= n ;i ++){__int64 ans = 0;for(j = 1 ;j <= 32 ;j ++){for(k = 1 ;k <= A[j] && k <= i ;k += 2){if(i - k > n - A[j]) continue;__int64 tmp = C[A[j]][k] * C[n - A[j]][i - k] % mod;ans = (ans + tmp * B[j]) % mod;}}if(i == 1) printf("%I64d" ,ans);else printf(" %I64d" ,ans);}printf("\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu4810 Cn中取i异或和的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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