题目意思就是给定n(≤1000)个整数，要求输出对于所有整数k(1..n)，该整数集合的所有元素个数为k的子集其元素的异或的和对M取模的值。
考虑所有包含于原集合的k子集的个数，当n=1000, k = 500的时候，(n, k)非常之大。
显然单个考虑某一k子集对和的贡献不是一个合适的切入点。
再仔细看看题目，要求的到底的是什么。
给定集合S, #(S) = n, 给定 k ≤ n, 求∑f(A) % M, 其中A ⊆ S，且 #(A) = k, f(A) = ^A[i], (A[i] ∈ A)。
我们用长度足够大(记为len)的二进制数重写整数（对于本题长度大于32即可）,假设整数a = str_A(binary form)
那么a^b = str_A ^ str_B = ∑(1 << i) * ((str_A[i] + str_B[i]) % 2) (i < len)。
也就是说，依次考察二进制串的每一位，若两个整数在该位上1的个数之和为奇数，则向两数异或中该位置贡献1，否则贡献0。
则f(A) = ^A[i] = ^ str_A[i] = ∑(1 << j) * (∑str_A[i][j] % 2) (j < len)。
到这里距离答案只有一步之遥了。
下面的问题在于怎么求∑f(A)。
这是一个求和，我们把j放在最外层循环。
那么我们有∑f(A)
= ∑(∑(1 << j) * (∑str_A[i][j] % 2)) (j < len)
= (1 << j) * ∑(∑str_A[i][j] % 2) ( j < len, str_A[i] 代表属于集合A中一个整数对应的二进制串，#(A) = k )
我们现在只考虑第j位上的情况。
我们知道每一个k子集最多向j位上贡献1，我们考虑所有k子集向j位上贡献多少。
假设原集合S中的数在第j位上依次是c[0], c[1], ..., c[n - 1]， 其中c[i]非0即1。
也就是我们向这n个数中取k个数，数一数取得的数中1有奇数个还是偶数个，若为奇数个则贡献1，否则贡献0。
我们假设n个数中1的个数为p, 0的个数为 n - p。
那么所有k子集在该位上的贡献值应该是(p, 1) * (n - p, k - 1) + (p, 3) * (n - p, k - 3) +...
具体过程见代码。
acm.hdu.edu.cn/showproblem.php?pid=4810
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 using namespace std; 6 typedef __int64 LL; 7 8 const int maxn = 1e3 + 10; 9 const int mod = 1e6 + 3; 10 11 int n; 12 int s[maxn]; 13 LL c[maxn][maxn]; 14 int ans[maxn]; 15 16 void init(){ 17 memset(c, 0, sizeof c); 18 c[0][0] = c[1][0] = c[1][1] = 1; 19 for(int i = 2; i <= 1000; i++){ 20 c[i][0]= c[i][i] = 1; 21 int mid = i / 2; 22 for(int j = 1; j <= mid; j++){ 23 c[i][i - j] = c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod; 24 } 25 } 26 } 27 28 void solve(){ 29 memset(ans, 0, sizeof ans); 30 for(int i = 30; i >= 0; i--){ 31 int f = 1 << i; 32 int cnt = 0; 33 for(int j = 0; j < n; j++) if(s[j] & f) ++cnt; 34 f %= mod; 35 for(int j = 1; j <= n; j++){ 36 for(int k = 1; k <= cnt && k <= j; k += 2){ 37 ans[j - 1] += ((c[cnt][k] * c[n - cnt][j - k]) % mod * f) % mod; 38 ans[j - 1] %= mod; 39 } 40 } 41 } 42 printf("%d", ans[0]); 43 for(int i = 1; i < n; i++) printf(" %d", ans[i]); 44 printf(" "); 45 } 46 47 int main(){ 48 init(); 49 while(~scanf("%d", &n)){ 50 for(int i = 0; i < n; i++) scanf("%d", &s[i]); 51 solve(); 52 } 53 return 0; 54 } 55 56 /* 57 0001 58 0010 59 1010 60 0001 61 */