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

Problem - D - Codeforces

題意：
給一個 01 字串，字符間或者左界右界放隔板。求至少放兩個隔板時，以二進位讀進所有被夾在隔板間的數字，令該數字集合中最大數為 x，則集合中所有數為正整數且含 [ 1, x ] 間所有數的方案數，對 1e9 + 7 取模。

資料規模：
字串長度 1 ≤ N ≤ 75
TL: 4000 ms
ML: 512 MB

解法：
因為字串長度最多只有 75，所以就算 1, 2, .. 所有正整數的集合全拿恰好一次，二進位長度總和限制了最多只能是 [ 1, 20 ] 的集合。因此可以 DP 起來不會太慘。轉移的部份因為有 leading zero 的問題，感覺不太妙，但因為題目限制不得有 0，所以可以預處理非零的下一個 ( 包括當前 ) 位子 O( 1 ) 轉移。想清楚的話，實現非常簡單。

時間 / 空間複雜度：
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;
}