DIV2 1000pt
题意：给定整数n和r，求有多少个这样的数列，a1，a2...an，使得a1 + a2 +...+an = a1|a2|a3|...|an，(按位或)。输出这样数列的个数mod 1000000009。
n <= 10，r <= 15000。
解法：先按位分析这道题，若将a1,a2..an转化成二进制形式并对齐如下，则可将题目转化为求每一列最多含有一个1，每一行所对应的数小等于r的矩阵有多少个。
这样的话，下意识地想到用状态压缩的DP来做，但是这样做的时间复杂度为O(10×15000×15000)，不能接受。最后我也没想出更好的方法，只好看了题解。
对于某一行，若要使得它对应的数小于r，只需要在某一列，r的二进制形式为1，它为0；在这一列之前， 该行所有值与r相同；在这之后，该行每一列可以为任意值。
设数组d[i][j]表示从左向右扫描的情况下，从第i位扫到第0位，已经有(n-j)个数小于r的情况下，共有多少个符合题意的数列。具体状态转移方程可以看我得代码，详细的注解见官方题解的代码，。
tag:dp, good
1 // BEGIN CUT HERE 2 /* 3 * Author: plum rain 4 * score : 5 */ 6 /* 7 8 */ 9 // END CUT HERE 10 #line 11 "YetAnotherORProblem2.cpp" 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 #include 25 #include 26 #include 27 #include 28 #include 29 #include 30 #include 31 #include
VI; 47 typedef vector
VS; 48 typedef vector VD; 49 typedef long long int64; 50 typedef pair pii; 51 52 const double eps = 1e-8; 53 const double PI = atan(1.0)*4; 54 const int maxint = 2139062143; 55 const int mod = 1000000009; 56 57 int r, n; 58 int64 d[35][15]; 59 60 int64 rec (int t, int num) 61 { 62 if (t == -1) return 1; 63 64 int64 &ret = d[t][num]; 65 int tmp = r & (1 << t); 66 67 if (ret != -1) return ret; 68 69 if (num == n){ 70 if (tmp) 71 return ret = (rec(t-1, 0) + n * rec(t-1, 1)) % mod; 72 return ret = rec(t-1, num); 73 } 74 if (num == 1){ 75 if (tmp) 76 return ret = (rec(t-1, 0) + rec(t-1, 1) + (n-1) * rec(t-1, 0)) % mod; 77 return ret = n * rec(t-1, 1) % mod; 78 } 79 return ret = (n+1) * rec(t-1, 0) % mod; 80 } 81 82 class YetAnotherORProblem2 83 { 84 public: 85 int countSequences(int N, int R){ 86 r = R; n = N; 87 CLR1 (d); 88 return (int)((rec(30, n)+mod) % mod); 89 } 90 91 // BEGIN CUT HERE 92 public: 93 void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); } 94 private: 95 template string print_array(const vector &V) { ostringstream os; os << "{ "; for (typename vector ::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); } 96 void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } } 97 //void test_case_0() { int Arg0 = 2; int Arg1 = 15000; int Arg2 = 4628299; verify_case(0, Arg2, countSequences(Arg0, Arg1)); } 98 void test_case_0() { int Arg0 = 2; int Arg1 = 2; int Arg2 = 7; verify_case(0, Arg2, countSequences(Arg0, Arg1)); } 99 void test_case_1() { int Arg0 = 2; int Arg1 = 3; int Arg2 = 9; verify_case(1, Arg2, countSequences(Arg0, Arg1)); }100 void test_case_2() { int Arg0 = 3; int Arg1 = 3; int Arg2 = 16; verify_case(2, Arg2, countSequences(Arg0, Arg1)); }101 void test_case_3() { int Arg0 = 7; int Arg1 = 1023; int Arg2 = 73741815; verify_case(3, Arg2, countSequences(Arg0, Arg1)); }102 103 // END CUT HERE104 105 };106 107 // BEGIN CUT HERE108 int main()109 {110 // freopen( "a.out" , "w" , stdout ); 111 YetAnotherORProblem2 ___test;112 ___test.run_test(-1);113 return 0;114 }115 // END CUT HERE View Code