首页 > 代码库 > Hdu 4810

Hdu 4810

2014-05-02 15:53:50

题目连接

2013年南京现场赛的题目,现场的时候,排在我们前面的队伍基本都过了这题,我们后面的队伍也有不少过了这题,唯独我们没有。。

后来是Qingyu Shao想到了思路,然后就让他来敲,我记得当时是C(n,k)打表的时候出现了问题,好弱。。于是乎就开始吃东西了。

回来之后就一直想A掉这题,但是一直没有思路。半年之后......今天问了下TYS,然后他给我讲了大体思路,才有点感觉。

 

大体思路:记录每一位上1的个数(这里只需要32位),对于第i天,必须要选出奇数个1才能使该位异或结果位1,否则为0。我们来看样例,

1 2 10 1

这4个数的二进制表示分别为:

0001

0010

1010

0001

比如第2天的时候, 从4个中选出2个来做异或,第4位上只有1个1,所以有3中选法可以使得这一位异或之后结果为1,(也就是C(3,1) * C(1,1)),第3位的没有1,所以异或结果一定为0,第2位上又2个1,所以有4种选法,同理第一位上也是4种。

所以其结果就是 (1<<3)*C(3,1) + 0 * C(4,2) + (1<<1)*C(2,1)*C(2,1) + (1<<0)*C(2,1)*C(2,1)

 

附上代码:

 1 /*************************************************************************
 2     > File Name: 4810.cpp
 3     > Author: Stomach_ache
 4     > Mail: sudaweitong@gmail.com
 5     > Created Time: 2014年05月02日 星期五 15时20分16秒
 6     > Propose: 
 7  ************************************************************************/
 8 
 9 #include <cmath>
10 #include <string>
11 #include <cstdio>
12 #include <fstream>
13 #include <cstring>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 
18 typedef long long LL;
19 #define MOD (1000000+3)
20 #define MAX_N (1000+3)
21 
22 int n;
23 int a[MAX_N], ans[MAX_N], c[MAX_N][MAX_N];
24 
25 void
26 init() {
27         c[0][0] = c[1][0] = c[1][1] = 1;
28         for (int i = 2; i < MAX_N; i++) {
29                 c[i][0] = 1;
30                 for (int j = 1; j <= i; j++) {
31                         c[i][j] = (c[i-1][j] + c[i-1][j-1]) % MOD;
32                 }
33         }
34 
35         return ;
36 }
37 
38 void
39 count(int x) {
40         for (int i = 0; i < 32; i++) {
41                 if (x & (1<<i)) {
42                         a[i]++;
43                 }
44         }
45 
46         return ;
47 }
48 
49 int
50 main(void) {
51         init();
52         while (~scanf("%d",&n)) {
53                 memset(a, 0, sizeof(a));
54                 for (int i = 0; i < n; i++) {
55                         int tmp;
56                         scanf("%d", &tmp);
57                         count(tmp);
58                 }
59 
60                 memset(ans, 0, sizeof(ans));
61                 for (int i = 1; i <= n; i++) {
62                         for (int j = 0; j < 32; j++) {
63                                 for (int k = 1; k <= a[j] && k <= i; k += 2) {
64                                         ans[i] = (ans[i] + (LL)c[n-a[j]][i-k]*c[a[j]][k]%MOD*((1 << j)%MOD) % MOD) % MOD;
65                                 }
66                         }
67                 }
68 
69                 for (int i = 1; i <= n; i++) {
70                         printf("%d%c", ans[i], i == n ? \n :  );
71                 }
72         }
73 
74         return 0;
75 }