首页 > 代码库 > 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 }
hdu 4810 Wall Painting
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。