首页 > 代码库 > hdu 4810 Wall Painting (组合数学+二进制)

hdu 4810 Wall Painting (组合数学+二进制)

2024-07-28 01:40:59   212人阅读

题目链接

下午比赛的时候没有想出来，其实就是int型的数分为30个位，然后按照位来排列枚举。

题意：求n个数里面，取i个数异或的所有组合的和，i取1~n

分析：

将n个数拆成30位2进制，由于每个二进制位异或后相加和原来的数异或相加是一样的，所以只需要对每一位累加计算，用组合数学取数就行了，奇数个异或得1，偶数个异或得0，再乘以自己的二进制位值，复杂度O（30*n*n）

 1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <queue> 5 #include <cstring> 6 #include <map> 7 #include <cstdlib> 8 #include <algorithm> 9 #define LL __int6410 #define INF 0x3f3f3f3f11 const int maxn = 1000+10;12 const int mo = 1000000+3;13 using namespace std;14 LL c[maxn][maxn], a[35], p[35];  //注意要用LL，中间计算会超int15 void init()16 {17     int i, j;18     memset(c, 0, sizeof(c));19     for(i = 0; i < maxn-5; i++)20     c[i][i] = c[i][0] = 1;21     for(i = 1; i < maxn-5; i++)22     for(j = 1; j < i; j++)23     c[i][j] = (c[i-1][j-1] + c[i-1][j])%mo;24 25     p[0] = 1;26     for(i = 1; i < 32; i++)27     p[i] = (2*p[i-1])%mo;28 }29 void cal(int x)30 {31     int cnt = 0;32     while(x)33     {34         if(x%2)35         a[cnt] ++;36         x /= 2;37         cnt ++;   //这个不要放到上面数组中，不然会在数组的下标多加一个38     }39 }40 int main()41 {42     int n, i, j, k, x;43     LL tmp, ans;44     init();45     while(~scanf("%d", &n))46     {47         memset(a, 0, sizeof(a));48         for(i = 0; i < n; i++)49         {50             scanf("%d", &x);51             cal(x);52         }53         for(i = 1; i <= n; i++)54         {55             ans = 0;56             for(j = 0; j < 32; j++)57             {58                 for(k = 1; k <= i; k += 2)59                 {60                     tmp = ((LL)(p[j]*c[a[j]][k]*c[n-a[j]][i-k]))%mo; //该位的数值 * 该位为1的个数选奇数个 * 为0的个数选空着的个数。61                      ans += tmp;62                     ans %= mo;63                 }64             }65             if(i == n)66             printf("%I64d\n", ans);67             else68             printf("%I64d ", ans);69         }70     }71     return 0;72 }

 

hdu 4810 Wall Painting (组合数学+二进制)


联系
我们