Hdu 4810

2014-05-02 15:53:50

题目连接

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

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

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

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

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)

附上代码：

 /*************************************************************************

     > File Name: 4810.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年05月02日 星期五 15时20分16秒

     > Propose:

  ************************************************************************/

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 #define MOD (1000000+3)

 #define MAX_N (1000+3)

 int n;

 int a[MAX_N], ans[MAX_N], c[MAX_N][MAX_N];

 void

 init() {

         c[][] = c[][] = c[][] = ;

         for (int i = ; i < MAX_N; i++) {

                 c[i][] = ;

                 for (int j = ; j <= i; j++) {

                         c[i][j] = (c[i-][j] + c[i-][j-]) % MOD;

                 }

         }

         return ;

 }

 void

 count(int x) {

         for (int i = ; i < ; i++) {

                 if (x & (<<i)) {

                         a[i]++;

                 }

         }

         return ;

 }

 int

 main(void) {

         init();

         while (~scanf("%d",&n)) {

                 memset(a, , sizeof(a));

                 for (int i = ; i < n; i++) {

                         int tmp;

                         scanf("%d", &tmp);

                         count(tmp);

                 }

                 memset(ans, , sizeof(ans));

                 for (int i = ; i <= n; i++) {

                         for (int j = ; j < ; j++) {

                                 for (int k = ; k <= a[j] && k <= i; k += ) {

                                         ans[i] = (ans[i] + (LL)c[n-a[j]][i-k]*c[a[j]][k]%MOD*(( << j)%MOD) % MOD) % MOD;

                                 }

                         }

                 }

                 for (int i = ; i <= n; i++) {

                         printf("%d%c", ans[i], i == n ? '\n' : ' ');

                 }

         }

         return ;

 }

巴特西

Hdu 4810

最新文章

热门文章