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;
}
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。