SRM 508 Div1 medium YetAnotherORProblem

問題概要

A0 + A1 + A2 + .... + An-1 == A0|A1|A2|....|An-1
で、
かつ、
Ai <= Ri
を満たすようなAiの数を数えよ。
Riの上限はだいたい、2^60くらい。

解法

dp
ビットを上から見ていく。
状態は上からiビット目までみていて、Ajのi番目のビットは自由に決められるかどうか。
Ajのi番目のビットにおいて、Ajのiビット目が1, でるとき、そこを0にすると下位ビットは自由に決められる。

ソース

#include<vector>
#include<bitset>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)

using namespace std;
typedef unsigned long long lli;

class YetAnotherORProblem {
public:
  int countSequences(vector<long long> R) {
    int N = 63, B = (1<< R.size());
    const lli MOD = 1000000009;
    lli dp[N][B];
    rep(i, N){
      rep(j, B){
        dp[i][j] = 0;
      }
    }
    dp[62][0] = 1;
    lli ret = 0;
    for(int i = 62; i>= 0; i--){
      rep(j, B){
        lli b = ((lli)1<<i);
        int next = j;
        //no 1
        rep(num, R.size()){
          if((j & (1 << num)) != 0)continue;
          if((R[num] & b) == 0LL)continue;
          next += (1<< num);
        }
        if(i == 0){
          ret += dp[i][j];
          ret %= MOD;
        }else {
          dp[i-1][next] += dp[i][j];
          dp[i-1][next] %= MOD;
        }
        //make 1
        rep(turn, R.size()){
          next = j;
          bool can = true;
          rep(num, R.size()){
            if((j&(1<<num)) != 0){
              continue;
            }
            if(turn == num){
              if((R[num] & b) == 0LL)can = false;
              continue;
            }
            if((R[num] & b) != 0LL){
              next += (1<<num);
            }
          }
          if(!can)continue;
          if(i == 0){
            ret += dp[i][j];
            ret %= MOD;
          }else {
            dp[i-1][next] += dp[i][j];
            dp[i-1][next] %= MOD;
          }
        }
      }
    }
    return ret;
  }
}