SRM592 Div1 Medium - LittleElephantAndPermutationDiv1

問題

長さnの順列a,bがあるとき、
magic(a,b) = max(a[1],b[1]) + max(a[2],b[2]) + ... + max(a[n],b[n])
と定義する
magic(a,b)の値がk以上になるようなa,bの組み合わせの数を求めよ

1 <= n <= 50
1 <= k <= 2500

解法

How to deal with two permutations? Matching DP - YouTube
この動画の解説がすごくわかりやすかった

片方の順列は{1,2,...,n}と固定しても問題はない
(それで数え上げた結果を最後にn!倍すれば良い)
すると↑の類題と同じような考え方ができるようになる
dp[i][j][L]: i番目まで見て、両方の順列それぞれでまだペアになっていない数字がj個あり、今までのmagic()の和がLであるような場合の数
各iでペアを確定するということはiがそのペアのmaxになるから容易に計算することができる
遷移はコードに書いてある通り

実装

dp配列は節約しないとスタックオーバーフローするから注意

#define reps(i,s,n) for(long long (i)=(s);(i)<(n);++(i))
#define rep(i,n) reps(i,0,n)

class LittleElephantAndPermutationDiv1 {
public:
	int getNumber(int n, int k) {
		ll dp[2][55][3030] = {};
		dp[0][0][0] = 1;
		rep(I,n) {
			int i = I&1;
			rep(j,n) rep(l,2525) {
				// l[i]とr[i]両方のペアをjから決める
				if (j) (dp[i^1][j-1][l+(I+1)*2] += dp[i][j][l]*j %mod *j) %= mod;
				// l[i]かr[i]どっちかのペアだけjから決める
				(dp[i^1][j][l+I+1] += dp[i][j][l]*j*2) %= mod;
				// l[i]とr[i]をペアにする
				(dp[i^1][j][l+I+1] += dp[i][j][l]) %= mod;
				// 何も決めない
				(dp[i^1][j+1][l] += dp[i][j][l]) %= mod;
			}
			memset(dp[i],0,sizeof(dp[i]));
		}
		ll res = 0;
		reps(i,k,2525) (res += dp[n&1][0][i]) %= mod;
		// 並べ方がn!通りある
		rep(i,n) (res *= i+1) %= mod;
		return res;
	}
};