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