首页 > 代码库 > hdu 4810 Wall Painting

hdu 4810 Wall Painting

http://acm.hdu.edu.cn/showproblem.php?pid=4810

把每一个数转化二进制,然后统计n个数在每一位的1的个数。奇数个1异或才能得1,然后用组合数,计算。

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int mod=1000003; 6  7 int n; 8 __int64 a[1100],num[1100],c[1100][1100],ans[1100]; 9 10 void inti()11 {12     for(int i=0; i<1100; i++)13     {14          c[i][0]=1;15          for(int j=1; j<=i; j++)16          {17              c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;18          }19     }20 }21 22 int main()23 {24     inti();25     while(scanf("%d",&n)!=EOF)26     {27         memset(num,0,sizeof(num));28         memset(ans,0,sizeof(ans));29         for(int i=1; i<=n; i++)30         {31             scanf("%I64d",&a[i]);32         }33         for(int i=0; i<=30; i++)34         {35             for(int j=1; j<=n; j++)36             {37                 if(a[j]&(1<<i)) num[i]++;38             }39         }40         for(int i=0; i<=30; i++)41         {42             for(int j=1; j<=n; j++)43             {44                 __int64 x=n-num[i];45                 if(num[i]==0) continue;46                 for(int k=1; k<=num[i]; k+=2)47                 {48                     if(j-k<=x&&j>=k)49                     {50                         ans[j]+=((c[num[i]][k]*c[x][j-k]%mod)*(1<<i))%mod;51                         ans[j]%=mod;52                     }53                 }54             }55         }56         printf("%I64d",ans[1]);57         for(int j=2; j<=n; j++)58         {59             printf(" %I64d",ans[j]);60         }61         printf("\n");62     }63     return 0;64 }
View Code

 

hdu 4810 Wall Painting