0w1

Bangladesh OI 2016 National Round pC. Counting Permutations ( DP )

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf
Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces

題意:
求有多少 [ 1, N ] 的排列,有至少 K 個逆序數對。

資料規模:
For easy version: 1≤ N≤ 200 and 0≤ K≤ 300. [40% of total score]
For hard version: 1≤ N≤ 2000 and 0≤ K≤ 3000. [100% of total score]
TL: 1000 ms
ML: 256 MB

解法:
感覺可以 N * K 所以要考慮 DP。有時候要靠直覺。
dp[ n ][ k ] : [ 1, n ] 的排列中,有恰好 k 個逆序數對的排列數。
想一下加入新的元素 n + 1 的時候會如何轉移:
放在最後一個:轉移至 dp[ n + 1 ][ k ]
插在最後一個的前面:轉移至 dp[ n + 1 ][ k + 1 ]
插在由後面數第 i ( 1 base ) 個的前面:轉移至 dp[ n + 1 ][ k + i ]
所以有了狀態 O( N * K ),轉移 O( N ) 的東西。
寫成遞迴式:
dp[ n ][ k ] = Sigma{ dp[ n - 1 ][ i ], for all max( 0, k - ( n - 1 ) ) ≤ i ≤ k }
因為轉移需要的總是連續和,所以可以開另一個 dp 維護 dp 的前綴和。轉移變成 O( 1 )

時間 / 空間複雜度:
O( N * K )

void solve(){
  int T; cin >> T;
  for( int kase = 1; kase <= T; ++kase ){
    cout << "Case " << kase << ": ";
    int N, K; cin >> N >> K;
    int ans = 1;
    for( int i = 1; i <= N; ++i ){
      ( ans *= i ) %= MOD;
    }
    if( K == 0 ){
      cout << ans << endl;
      continue;
    }
    vvi dp( N + 1, vi( K ) );
    vvi pdp( N + 1, vi( K + 1 ) );
    dp[ 0 ][ 0 ] = 1;
    for( int i = 0; i < K; ++i ){
      pdp[ 0 ][ i + 1 ] = pdp[ 0 ][ i ] + dp[ 0 ][ i ];
    }
    for( int i = 1; i <= N; ++i ){
      for( int j = 0; j < K; ++j ){
        dp[ i ][ j ] = ( pdp[ i - 1 ][ j + 1 ] - pdp[ i - 1 ][ max( 0, j - ( i - 1 ) ) ]  )% MOD;
        pdp[ i ][ j + 1 ] = ( pdp[ i ][ j ] + dp[ i ][ j ] ) % MOD;
      }
    }
    /* for( int i = 0; i < N; ++i ){ // slow version
      for( int j = 0; j < K; ++j ){
        for( int k = 0; k <= i; ++k ){
          if( j + k >= K ) continue;
          ( dp[ i + 1 ][ j + k ] += dp[ i ][ j ] ) %= MOD;
        }
      }
    } */
    for( int i = 0; i < K; ++i ){
      ( ans -= dp[ N ][ i ] ) %= MOD;
    }
    if( ans < 0 ) ans += MOD;
    cout << ans << endl;
  }
}