Hdu 4810

11009 ワード

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つしかないので、3つの中選法でこの1つの異或の後に結果が1、(つまりC(3,1)*C(1,1))となり、3位には1がないので、異或の結果は必ず0、2位に2つの1となるので、4つの選法があり、同じ理屈で1位にも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)*C(2,1)
 
コードを添付:
 1 /*************************************************************************

 2     > File Name: 4810.cpp

 3     > Author: Stomach_ache

 4     > Mail: [email protected]

 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 ? '
' : ' '); 71 } 72 } 73 74 return 0; 75 }