SRM 508 Div1 Medium YetAnotherORProblem

shioshiotaさんのブログ見てようやく理解できた。。。
id:shioshiota:20110613:1307955077

問題

数列R[i]（0≦i＜n）が与えられる。
次の条件を満たすような数列がいくつあるか、mod 1000000009で求めよ。

A[0] + A[1] + … + A[n-1] = A[0] | A[1] | … | A[n-1]
かつ
A[i]≦R[i]

制約条件

n≦10
R[i]≦10^18

方針

まず、A[0],A[1],...,A[n-1]のiビット目のうち、1になっているものはただ一つだけである。
（そうでなければA[0] + A[1] + … + A[n-1] > A[0] | A[1] | … | A[n-1]になるため）

A[j]を、上位ビットiから、A[j]のうち高々1つどれを1にするかの決定していく。
R[j]のiビット目が1で、A[j]のiビット目を0にすると、A[j]のi-1ビット目以下は全て自由に決定できる。

dp[i][mask]を上からiビットまでを見て、集合maskのビットを自由に決定できるような数列A（のiビット目まで）の場合の数とすると、n個のAのうちどのiビット目を1にするかでテーブルの更新ができてDPできる。

ビットを1にできるA[j]は、集合maskに含まれているjまたは、R[j]のiビット目が1であるようなjである。

ソースコード

const int mod = 1000000009;

class YetAnotherORProblem {
  public:
  int countSequences(vector<long long> R) {
    int n=R.size(), dp[65][1<<10]={}, ans=0;
    dp[62][0]=1;

    for(int i=62;i>=0;i--)rep(mask,1<<n){
        
        int nmask=mask;
        //A[0]〜A[n-1]のiビット目を全部0にする
        rep(k,n)if(R[k]&1ll<<i)nmask|=1<<k;
        if(i)(dp[i-1][nmask]+=dp[i][mask])%=mod;
        else (ans+=dp[i][mask])%=mod;

        //A[j]のi番目のビットを1にする
        rep(j,n){
          //maskにjが含まれているもしくはR[j]のiビット目が1の時だけA[j]のiビット目は1にできる。
          if(!(mask&1<<j)&&!(R[j]&1ll<<i))continue;
          
          nmask=mask;
          rep(k,n){
            //R[k]のiビット目が1のところを0にしたら、A[k]のi-1ビット目以下は自由になる。
            //（のでmaskにkを加える）
            if(j!=k&&(R[k]&1ll<<i))nmask|=1<<k;
          }
          if(i)(dp[i-1][nmask]+=dp[i][mask])%=mod;
          else (ans+=dp[i][mask])%=mod;
        }
      }
    return ans;
  }
};