Hatena::Grouptopcoder

shnyaの参戦記録

2011-06-07練習

SRM 508 Div2 Hard YetAnotherORProblem2 02:16  [http://www.topcoder.com/stat?c=problem_statement&pm=11435&rd=14437:title=SRM 508 Div2 Hard YetAnotherORProblem2] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=11435&rd=14437:title=SRM 508 Div2 Hard YetAnotherORProblem2] - shnyaの参戦記録

1 <= a_i <= Rの整数からなるN個の配列がある。

a_1 | a_2 | ... | a_n-1 | a_n = a_1 + a_2 + ... + a_n-1 + a_nとなるような並びは何通りあるか。

(|はOR演算)


ビットDPかなぁと思って考えてみるも、空間計算量がO(NR^2)ぐらいになってしまってちょっと厳しいなぁと思い、考え続けるも答えが出ない。


なんとか次元をひとつ落とせばなんとかなるかなぁといいなぁと思いつつも浮かばない。解いた人のコード見て、あぁ、こういう風に解けばいいのかと納得した。

ビットの部分集合を列挙するループの書き方はSigmarさんのブログを参考にしました。

http://topcoder.g.hatena.ne.jp/jackpersel/20100804/1281196966

LLI M = 1000000009LL;
LLI dp[2][1<<14];

class YetAnotherORProblem2 {
public:
  int countSequences( int N, int R ) {
    memset(dp,0,sizeof dp);
    for(int j = 0; j <= R; j++)
      dp[0][j] = 1;

    for(int i = 1; i < N; i++){
      for(int j = 0; j < (1 << 14); j++){
        dp[i%2][j] = dp[(i-1)%2][j];
        for(int k=j; k>0; k=(k-1)&j){
          if(k <= R){
            dp[i%2][j] += dp[(i-1)%2][j-k];
            dp[i%2][j] %= M;
          }
        }
      }
    }
    LLI res = 0;
    int last = (N-1)%2;
    for(int i = 0; i < (1 << 14); i++){
      res += dp[last][i];
      res %= M;
    }
    return res;
  }
};