Yuki 389 ロジックパズルの組み合わせ ( Combinatorics, Math )

No.389 ロジックパズルの組み合わせ - yukicoder

題意：
在一排 M 個格子上放黑色點，依序為 H[ 0 ], H[ 1 ] .. H[ N ] 個連續的黑色點，且兩兩以至少一個的連續白色點區隔。求模 1e9 + 7 後的方案數。

資料規模：
1 ≤ M < 1e6
0 ≤ H[ i ]
SIGMA{ H } ≤ M
保證若有一個 H 為 0，則只會有一個 H。

解法：
首先把必須有的樣貌構造出來，那就是倆倆之間洽有一個白色格子，因此 M 不能小於 SIGMA{ H } + SIZE( H ) - 1。如果有多的格子可以放，我們有 SIZE( H ) + 1 個地方可以放 ( 含兩端 )。因此變成重複排列的問題。

時間 / 空間複雜度：
O( N lg MOD7 ) / O( N )

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

int M;
vi H;

void init(){
  cin >> M;
  int h;
  while( cin >> h )
    if( h )
      H.emplace_back( h );
}

int n, m;
int sum_h;

int int_pow( int v, int p ){
  int res = v != 0 or p == 0;
  while( p ){
    if( p & 1 )
      res = 1LL * res * v % MOD7;
    p >>= 1;
    v = 1LL * v * v % MOD7;
  }
  return res; 
}

int mod_inv( int v ){
  return int_pow( v, MOD7 - 2 );
}

int comb( int n, int m ){
  int res = 1;
  for( int i = 2; i <= n; ++i )
    res = 1LL * res * i % MOD7;
  for( int i = 2; i <= m; ++i )
    res = 1LL * res * mod_inv( i ) % MOD7;
  for( int i = 2; i <= n - m; ++i )
    res = 1LL * res * mod_inv( i ) % MOD7;
  return res;
}

void preprocess(){
  for( int i = 0; i < H.size(); ++i )
    sum_h += H[ i ];
  n = M - ( sum_h + H.size() - 1 ); // number of free balls
  m = H.size() + 1; // number of choices to put free balls
  if( n < 0 )
    cout << "NA" << endl, exit( 0 );
}

void solve(){
  cout << comb( m + n - 1, n ) << endl;
}