SRM 508 div1 med:YetAnotherORProblem

このDPは思いつかなかった…
良い問題。

問題

TopCoder Statistics - Problem Statement

解法

まず気づかないといけないのは「和がorの和と等しくなるならすべてのa[i]について2進法で表した時のbitの1がかぶっていない」ということです。軽く説明すると,3つの数を2進数で表した時に
10001
01101
00010
のようになっていると,0bit目の1が1番目の数と2番目の数でかぶっているのでこの場合は和とorの和が等しくなりません。一方で,
10010
01001
00100
のようになっていると,すべての桁で1が被ってないので和とor和が等しくなります。

ということで,このように1が2進数の各桁で被らないような場合の数を求めたいのですが,これを解くためにdpが出てきます。

ちょっと前提ですがstateという変数を用意します。これは,各値a[i]がR[i]未満であるというフラグをn個分並べたものです。
以下のdpではn桁目を見る時「それぞれの数a[i]がR[i]より小さくなっているか」ということを大事にしています。

dp[n][state]=(2進数のn桁目から初めてn番目の桁を見ている時,各a[i]がR[i]未満であるフラグがstateであるような場合の数)
とします。

すると,「stateという状態のもとでa[j]だけがi桁目について1になる」という場合の数は,以下のような状態へ派生します。

j以外の各kについて,R[k]のi桁目が1ならa[k]がR[k]未満であることが確定するのでnext_stateをそのように更新する

で,このnext_stateに状態が遷移するので
dp[n-1][next_state] += dp[n][state]
とやっていけば良いです。

なお,すべての桁が0でも良いのでその場合も特別に設ける必要があります。下のコードではj==nのときすべてのi桁目が0である場合として扱っています。

const ll MOD = 1e9+9;
const int MAXN = 11;
ll dp[62][1<<MAXN];

class YetAnotherORProblem {
public:
    int countSequences(vector<long long> R) {
        memset(dp, 0, sizeof(dp));
        dp[60][0] = 1;
        int n = R.size();
        for (int i = 59; i >= 0; i--) {
            for (int s = 0; s < (1<<n); s++) {
                for (int j = 0; j <= n; j++) {
                    if (j == n || (s>>j)&1 || (R[j]>>i)&1) {
                        // j番目の数のi bit目を1にします
                        // n番目のi bit目を1にする=i bit目は全部0
                        int ns = s;
                        for (int k = 0; k < n; k++) {
                            if (k == j) continue;
                            if ((R[k]>>i)&1) ns |= (1<<k);
                        }
                        (dp[i][ns] += dp[i+1][s]) %= MOD;
                    }
                }
            }
        }
        ll ans = 0;
        for (int i = 0; i < (1<<n); i++) {
            (ans += dp[0][i]) %= MOD;
        }
        return ans;
    }
};