SRM508 Div1 Medium(500) YetAnotherORProblem

論理和と和が等しくなるのは、2進数でi桁目が1であるA_xの個数が高々1個の場合。各桁ごとにA_xのどれか1個に1を割り振るか、全てを0にする、場合の数を考える。

A_iのj桁目に値を割り振る時、A_i≦R[i]を満たすためには、R[i]のj桁目が1ならば0でも1でも良いが、R[i]のj桁目が0ならば、jより上の桁でR[j]が1のところに0を割り振った場合のみ0でも1でも良い。そうでなければ0のみ。

R[0],R[1],…,R[N-1]が1の場合に0を割り振ったかどうかごとに、場合の数を覚えて置いて、動的計画法。

#include <vector>
using namespace std;

class YetAnotherORProblem{public:
int countSequences( vector<long long> R )
{
    int M = 1000000009;
    int N = (int)R.size();

    vector<long long> T(1<<N,1);

    for ( int i=0; i<63; i++ )
    {
        vector<long long> P = T;
        T = vector<long long>(1<<N,0);

        for ( int f=0; f<(1<<N); f++ )
        {
            //  0 - n-1: Ajのi番目のビットを立てる
            //  n      : ビットを立てない
            for ( int j=0; j<=N; j++ )
            if ( f>>j&1 || j>=N || R[j]>>i&1 )
            {
                int t = f;
                for ( int k=0; k<N; k++ )
                if ( k!=j && R[k]>>i&1 )
                    t |= 1<<k;
                T[f] = (T[f]+P[t])%M;
            }
        }
    }

    return (int)T[0];
}};