ABC134 F - Permutation Oddness (600)

F - Permutation Oddness

概要

数列{1, 2, ..., N}の順列{p1, p2, ..., pN}の奇妙さをΣ|pi - i| で定義する。
Σ|pi - i| = k なる順列の個数を求めよ。(mod 10^9 + 7 して出力)

制約

1 ≦ N ≦ 50
0 ≦ K ≦ N * N
(もとの問題はN, Kともに小文字)

方針

DPが使える。

1からNまで番号付けされた玉と箱があり、玉を箱に入れる。
すべての玉を箱に入れたとき箱iに入っている玉の番号をpiとし、この箱への玉の入れ方を考える。

箱・玉の番号を前から見ていき、i番目の箱・玉の時点で玉をそのまま箱に入れる方法と、箱・玉のいずれかもしくは両方を「保留」しておき、のちの箱・玉に入れる方法を考えると、順列が再現できそう。

一見すると、保留している箱・玉の番号を全て覚えておく必要があるように思えるが、実はこれは保留している箱・玉の個数だけを持っておくとうまくいく。

また、「奇妙さ」の計算については、(i, j, k) = (見た箱・玉の個数, 保留している箱・玉の個数, 現在の奇妙さ)とすると、(i, j, k)からi+1への遷移ではどのような箱・玉の入れ方の場合もk ⇒ k + 2 *j へと遷移する。

具体的なDPは次の通り。
dp[i][j][k] := 見た箱・玉の個数がi、保留している箱・玉の個数がj、現在の奇妙さがkであるときの順列の個数
遷移は、「今の玉を今の箱に入れる」1通り + 「今の玉を保留する or 保留箱に入れる」 * 「今の箱を保留する or 保留玉を入れる」4通りで計5通り。

感想

アルメリアさんのブログを大いに参考にしました。
betrue12.hateblo.jp

解答

Submission #6640226 - AtCoder Beginner Contest 134

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
ll MOD = 1e9+7;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N, K;
	cin >> N >> K;
 
	static ll dp[51][51][2501];
	rep(i, N+1) rep(j, N+1) rep(k, N*N+1) dp[i][j][k] = 0;
	dp[0][0][0] = 1;
 
	rep(i, N) rep(j, N) rep(k, K+1){
		if(k + 2*j > N*N) continue;
 
		// 今の玉を今の箱に入れる
		dp[i+1][j][k+2*j] += dp[i][j][k];
		dp[i+1][j][k+2*j] %= MOD;
 
		// 今の玉を保留箱に入れ、今の箱を保留
		dp[i+1][j][k+2*j] += j * dp[i][j][k];
		dp[i+1][j][k+2*j] %= MOD;
 
		// 今の玉を保留箱に入れ、今の箱に保留玉を入れる
		if(j-1 >= 0){
			dp[i+1][j-1][k+2*j] += j * j * dp[i][j][k];
			dp[i+1][j-1][k+2*j] %= MOD;
		}
 
		// 今の玉を保留、今の箱に保留玉を入れる
		dp[i+1][j][k+2*j] += j * dp[i][j][k];
		dp[i+1][j][k+2*j] %= MOD;
 
		// 今の玉を保留、今の箱も保留
		if(j+1 <= N){
			dp[i+1][j+1][k+2*j] += dp[i][j][k];
			dp[i+1][j+1][k+2*j] %= MOD;
		}
	}
 
	cout << dp[N][0][K] << endl;
}