HDU4810_Wall Painting

题目很简单。

给你n个数，输出n个答案，第i个答案表示从n个数里取遍i个数的异或值的和。

其实每一个数最多也就32位，把所有的数分解，保存每一位总共有多少个1，最后要是这一位的异或结果为1，那么在所有的异或数中，这一位为1的数必须是有奇数个，在求解的时候就是求组合数的情况就可以了。

直接水过。

#include <iostream>

#include <cstdio>

#include <cstring>

#define M 1000003

#define maxn 1005

typedef long long ll;

using namespace std;

int a[];

int ans,n,m,k,c[maxn][maxn],u[];

ll tep;

void insert(int x)

{

    for (int cur=; x; cur++,x>>=) a[cur]+=x&;

}

void init_c()

{

    u[]=;

    for (int i=; i<=; i++) u[i]=(u[i-]+u[i-])%M;

    c[][]=;

    c[][]=c[][]=;

    for (int i=; i<maxn; i++)

    {

        c[i][]=;

        for (int j=; j<=i; j++)

            c[i][j]=(c[i-][j]+c[i-][j-])%M;

    }

}

int main()

{

    init_c();

    while (scanf("%d",&n)!=EOF)

    {

        memset(a,,sizeof a);

        for (int i=; i<=n; i++) scanf("%d",&k),insert(k);

        for (int i=; i<=n; i++)

        {

            ans=;

            for (int j=; j<=; j++)//每一位为1的情况

            {

                for (k=; k<=a[j] && k<=i; k+=)

                {

                    if (i-k>n-a[j]) continue;

                    tep=(ll)c[a[j]][k]*c[n-a[j]][i-k];

                    tep%=M;

                    tep=(tep*u[j])%M;

                    ans+=tep;

                    if (ans>=M) ans-=M;

                }

            }

            if (i>) printf(" ");

            printf("%d",ans);

        }

        printf("\n");

    }

    return ;

}