# CFR 757 D. Felicity's Big Secret Revealed ( DP )

Problem - D - Codeforces

TL: 4000 ms
ML: 512 MB

O( N * 2^20 * 5 ) / O( N * 2^20 )

```const int MOD7 = ( int ) 1e9 + 7;

int N;
string seq;

void init(){
cin >> N;
cin >> seq;
}

const int MAXN = 75;
const int MAGIC = 20;

int dp[ MAXN + 1 ][ 1 << MAGIC ];
int nxt[ MAXN ]; // next position not 0 ( possibly current position )

int valid( int s ){ // assert( s != 0 );
int a = __builtin_popcount( s );
int b = 32 - __builtin_clz( s );
return a == b;
}

void solve(){
for( int i = N - 1, f = N; i >= 0; --i ){
if( seq[ i ] == '1' ){
f = i;
}
nxt[ i ] = f;
}
for( int i = 0; i < N; ++i ){
dp[ i ][ 0 ] = 1;
}
for( int i = 0; i < N; ++i ){
for( int j = 0; j < 1 << MAGIC; ++j ){
int v = 0;
for( int k = nxt[ i ]; k < N; ++k ){
v = v * 2 + seq[ k ] - '0';
if( v > 20 ) break;
( dp[ k + 1 ][ j | 1 << v - 1 ] += dp[ i ][ j ] ) %= MOD7;
}
}
}
int ans = 0;
for( int i = 1; i <= N; ++i ){
for( int j = 1; j < 1 << MAGIC; ++j ){
if( not valid( j ) ) continue;
( ans += dp[ i ][ j ] ) %= MOD7;
}
}
cout << ans << endl;
}
```