abc134F题解

abc134F
题意：
定义长度为\(n\)的排列的怪异值为\(\sum_{i=1}^{n} \mid p_i-i\mid\)，问长度为\(n\)，怪异值为\(k\)的排列数。
思路：
非常妙的dp题。
\(\mid p_i-i\mid\)可以看成上下两层数，将上层中的\(i\)和下层中的\(j\)匹配，怪异值增加\(i\)，\(j\)中较大值减较小值。
整体思路为从小到大枚举\(i\)，如果将\(i\)和前面的位置匹配，怪异值加\(i\)，否则怪异值减\(i\)。
设计状态\(f_{i,j,k}\)表示前\(i\)对数，\(j\)对数未匹配，且怪异值为\(k\)的方案数。
转移：
1.\(i\)的上下层都不匹配，\(f_{i-1,j-1,k+2*i}\to f_{i,j,k}\)。
2.\(i\)的上层或下层中的一个和前面的匹配，或\(i\)的上下层互相匹配，\(f_{i-1,j,k}\times (2*j+1)\to f_{i,j,k}\)。
3.\(i\)的上层和下层都与前面的匹配，\(f_{i-1,j+1,k-2*i}\times (j+1)^2\to f_{i,j,k}\)。
代码：

#include<iostream>
#define int long long
#define mod 1000000007
using namespace std;
int n,k;
int f[60][60][6010];
signed main(){
	cin>>n>>k;
	f[0][0][n*n+2*n]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=i;j++){
			for(int l=-n*n;l<=n*n;l++){
				f[i][j][l+n*n+2*n]=(f[i-1][j][l+n*n+2*n]*(2*j+1)+f[i-1][j+1][l+n*n+2*n-2*i]*(j+1)*(j+1))%mod;
				if(j!=0){
					f[i][j][l+n*n+2*n]=(f[i][j][l+n*n+2*n]+f[i-1][j-1][l+n*n+2*n+2*i])%mod;
				}
			}
		}
	}
	cout<<f[n][0][k+n*n+2*n];
	return 0;
}