D - Wall Painting

思路：

（1）条件+问题：给定n个数，求其中任意k个数的组合的异或和，k取1~n全部求一遍；

（2）分析：

1. 凡是异或率先考虑二进制，由于求的是所有情况的异或和，即每一位都得讨论所有异或情况，而每种情况的异或若不为0，则必然记录，所以考虑逐位讨论所有情况，若不为0则加和；
2. 对于每一位，若有x个1，n - x个0，若k中选了i个1，选k个的组合方式即为                                                                            C（x,i)*C(n - x,k - i)
3. 显然当且仅当i为奇数时才有统计必要，所以i(1~k)枚举任意奇数可能，对于每种i，统计其组合可能数，于是就拿到了各位的1的加和次数；
4. 对于每位的1，按位权进行加和即可；

代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
 
typedef long long LL;
#define MOD (1000000+3)
#define MAX_N (1000+3)
 
int n;
int a[MAX_N], ans[MAX_N], c[MAX_N][MAX_N];
 
void init()
{
    c[0][0] = c[1][0] = c[1][1] = 1;
    for (int i = 2; i < MAX_N; 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 ;
}
 
void count(int x)
{
    for (int i = 0; i < 32; i++)
    {
        if (x & (1<
        {
            a[i]++;
        }
    }
 
    return ;
}
 
int main()
{
    int n;
    init();
    while(scanf("%d",&n)!=EOF)
    {
        memset(a, 0, sizeof(a));
        for(int i=1; i<=n; i++)
        {
            int x;
            cin>>x;
            count(x);
        }
        memset(ans, 0, sizeof(ans));
 
        for(int i=1; i<=n; i++)
            for(int j=0; j<32; j++)
                for(int k=1; k<=a[j]&&k<=i; k+=2)
                    ans[i]=(ans[i]+(LL)c[a[j]][k]*c[n-a[j]][i-k]%MOD*((1 << j)%MOD) % MOD) % MOD;
 
        for (int i = 1; i <= n; i++)
        {
            printf("%d%c", ans[i], i == n ? '\n' : ' ');
        }
 
    }
}