SRM508 Div2 Hard(1000) 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; }};