首页 > 代码库 > Hdu 4810

Hdu 4810

2024-07-02 15:01:45   225人阅读

2014-05-02 15:53:50

题目连接

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

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

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

 

大体思路：记录每一位上１的个数（这里只需要３２位），对于第i天，必须要选出奇数个１才能使该位异或结果位１，否则为０。我们来看样例，

4 

1 2 10 1

这４个数的二进制表示分别为：

0001

0010

1010

0001

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

所以其结果就是　(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 }

 

 

 


联系
我们