PKU 2323 PERMS
問題
1〜nの順列のうち、転置がちょうどk個あるようなものはいくつあるか、求めよ。
制約条件
n≦18
方針
dp[n][k]を長さがnの順列に転置がk個あるとしてメモ化再帰。
最初に、残っているうちでi番目に小さい数を使うと、
場合の数はdp[n - 1][k - i - 1]になるので、漸化式が立つ。
ソースコード
ll dp[50][200]; ll rec(int n, int k){ if(k < 0) return 0; ll &res = dp[n][k]; if(res >= 0) return res; if(n == 1) return res = k == 0 ? 1 : 0; res = 0; rep(i, n) res += rec(n - 1, k - i); return res; } int main(){ int n, k; memset(dp, -1, sizeof(dp)); while(cin >> n >> k, n){ cout << rec(n, k) << endl; } return 0; }