AtCoder ABC #134 : F - Permutation Oddness

うーん、遠回りしすぎた。
https://atcoder.jp/contests/abc134/tasks/abc134_f

問題

２整数N,Kが与えられる。
1～NのPermutation Pのうち、|i-P[i]|の総和がちょうどKとなるのは何通りか。

解法

1～Nのラベルを持つ頂点が左から順に並んでいる有向グラフを考えよう。
各頂点は入次数・出次数がともに1だとし、自己辺も許容されるとする。

辺の長さを頂点のラベル番号の差とすると、問題はこのグラフにおいて辺の長さの総和がKになるものを求める問題となる。
i番と(i+1)番の頂点の間をまたがる辺が右向き・左向きにx本ずつある場合、長さの総和には2xだけ寄与する。
これを用いて数え上げていく。

ここで以下を考えよう。
dp(i,x,y) := i番目までの頂点が出入りする辺の左右を決めたとき、i番より右向きに出ている出ている辺(とi番より右の頂点から左向きに受ける辺)がx本であり、かつi番目までの頂点における辺の長さの総和がyであるときの組み合わせ。

dp(0,0,0)から初めて、dp(N,0,K)を求めよう。
dp(i-1,x,y)からi番目の頂点の辺を考えるとき、以下のように遷移する。

• 左から右向きに来る辺を受け、また出ていく辺は左向きとする。それぞれどの辺と対応付けるかx通りあるので、dp(i,x-1,y+2x) += dp(i-1,x,y)*x^2
• 右から左向きに来る辺を受け、また出ていく辺は右向きとする。dp(i,x+1,y+2x) += dp(i-1,x,y)
• 左から右向きに来る辺を受け、また出ていく辺は右向きとする。受ける辺がx通りなのでdp(i,x,y+2x) += dp(i-1,x,y)*x
• 右から左向きに来る辺を受け、また出ていく辺は左向きとする。受ける辺がx通りなのでdp(i,x,y+2x) += dp(i-1,x,y)*x
• 自己辺を張る。dp(i,x,y+2x) += dp(i-1,x,y)

int N,K;
ll mo=1000000007;
ll pat[55][55][5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N>>K;
	
	pat[0][0][0]=1;
	for(i=1;i<=N;i++) {
		FOR(x,i) FOR(y,N*N) if(pat[i-1][x][y]) {
			ll v=pat[i-1][x][y];
			// close
			if(x) (pat[i][x-1][y+2*x]+=v*(x*x))%=mo;
			// open
			(pat[i][x+1][y+2*x]+=v)%=mo;
			// concat+self
			(pat[i][x][y+2*x]+=v*(2*x+1))%=mo;
		}
		
	}
	cout<<pat[N][0][K]<<endl;
}

まとめ

方針ガチャを失敗しているのに、考察不足のまま実装始めてしまい10分以上タイムロスしたのは反省…。