Hdu 4810
11009 ワード
2014-05-02 15:53:50
タイトル接続
2013年の南京の現場試合のテーマは、現場の時、私たちの前に並んだチームはほとんどこの問題を通過しました.私たちの後ろのチームもこの問題を通過したことがありますが、私たちだけはありません.
それからQingyu Shaoが考えを思いついて、それから彼に叩かせて、私は当時C(n,k)が時計を打った時に問題があったことを覚えていて、とても弱いです.そこで何かを食べ始めた.
帰ってきてからずっとAがこの問題を落とすと思っていたが、ずっと考えられなかった.半年後...今日TYSを聞いて、彼は私に大体の考えを話してくれて、やっと少し感じました.
大まかな考え方:各上位1の個数(ここでは32ビットしか必要としない)を記録し、i日目には、そのビットを異ならせるか結果ビット1にするには奇数の1を選択しなければならない.そうしないと0になる.サンプルを見てみましょう
4
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)
コードを添付:
タイトル接続
2013年の南京の現場試合のテーマは、現場の時、私たちの前に並んだチームはほとんどこの問題を通過しました.私たちの後ろのチームもこの問題を通過したことがありますが、私たちだけはありません.
それからQingyu Shaoが考えを思いついて、それから彼に叩かせて、私は当時C(n,k)が時計を打った時に問題があったことを覚えていて、とても弱いです.そこで何かを食べ始めた.
帰ってきてからずっとAがこの問題を落とすと思っていたが、ずっと考えられなかった.半年後...今日TYSを聞いて、彼は私に大体の考えを話してくれて、やっと少し感じました.
大まかな考え方:各上位1の個数(ここでは32ビットしか必要としない)を記録し、i日目には、そのビットを異ならせるか結果ビット1にするには奇数の1を選択しなければならない.そうしないと0になる.サンプルを見てみましょう
4
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 }