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

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

dp[ n ][ k ] : [ 1, n ] 的排列中，有恰好 k 個逆序數對的排列數。

dp[ n ][ k ] = Sigma{ dp[ n - 1 ][ i ], for all max( 0, k - ( n - 1 ) ) ≤ i ≤ k }

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;
}
}
```