SRM508 Div2 Hard(1000) YetAnotherORProblem2

YetAnotherORProblem2

Div1の問題よりサイズが小さいので簡単。各桁でビットが立っているのがA0,A1,……,AN-1のうち高々1個であれば良い。k&=jは(j|k)==jとなるようなjを列挙するため。参照。単純に0≦k≦Rでループすると惜しいところでTLEだった。

class YetAnotherORProblem2{public:
int countSequences( int N, int R )
{
    const int M = 1000000009;
    const int S = 0x4000;   //  15000以上で最小の2^x

    static int T[11][S];
    for ( int i=0; i<=N; i++ )
    for ( int j=0; j<S; j++ )
        T[i][j] = 0;
    T[0][0] = 1;

    for ( int i=1; i<=N; i++ )
    for ( int j=0; j<S; j++ )
    for ( int k=j; k>=0; k-- )
    {
        k &= j;
        if ( k <= R )
            T[i][j] = (T[i][j]+T[i-1][j^k])%M;
    }

    int ans = 0;
    for ( int i=0; i<S; i++ )
        ans = (ans+T[N][i])%M;
    return ans;
}};