SRM 508 Div2 Hard YetAnotherORProblem2

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11435&rd=14437
N、Rが与えられる。
$a_i \le R$ かつ $\displaystyle{\sum_{i=0}^{N-1}{a_i}}=a_0|a_1|\cdots|a_{N-2}|a_{N-1}$ となる数列の個数を求めよ。

やりかた

N個の項のある桁のビットを取り出した時に、それらのビットが1であるのが高々1以下であり、これがすべての桁について成り立つとき上の式が成立する。
つまり
a1 11000010
a2 00101000
a3 00010001
みたいになっているときに式は成立する。
Rが2^n - 1という形をしたメルセンヌ数であると答えはただのべき乗計算でとても簡単なのだけれど、そうではないので普通にbitDPをするのが良い。

dp[i][j]:=（項 $a_i$ までの論理和がjであるときの、そのような数列の個数）
でDP。すると
$dp[i][j] = \sum_{k}{dp[i - 1][k \ xor \ j]}$ となる。kはjをビットの集合として見た時のjの部分集合である。やっていることはSRM 474 Div2 Hardと同じようなこと。ただし今回はjの部分集合として空集合も許す（つまりk==0も想定する）ため上の部分集合列挙の方法ではまずい。空集合も含めた部分集合の列挙方法はSigmarさんのこの記事をご参照ください。

以下ソース。

int MOD = 1000000009;
const int NUM = 1 << 14;

class YetAnotherORProblem2 {
public:
  int dp[11][NUM];
  int countSequences(int N, int R) {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i = 1; i <= N; i++)
      for(int j = 0; j < NUM; j++)
	for(int sub = j; sub >= 0; sub--){
	  sub &= j;
	  if(sub <= R)
	    dp[i][j] = (dp[i][j] + dp[i - 1][j ^ sub]) % MOD;
	}

    int ans = 0;
    for(int i = 0; i < NUM; i++)
      ans = (ans + dp[N][i]) % MOD;
    return ans;
  }
}