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; } }