题目大意
定义一个 \(1 \sim n\) 的排列 \(p\) 的「怪异度」为
\[\sum_{i=1}^n|p_i-i| \]求「怪异度」为 \(m\) 的 \(1 \sim n\) 的排列数,答案对 \(10^9+7\) 取模。
思路
考虑把 \(p_i\) 和 \(i\) 看作小球与盒子,方便题意理解。
考虑球与盒子的匹配。
假设球在左侧,盒子在右侧,他们构成了一个二分图。
从上到下顺着排列每组球与盒子,球与盒子之间有一条横线。
我们发现,假设第 \(i\) 个盒子与 \(j\) 个球相连,他们之间的距离为 \(\left\lvert i - j \right\rvert\),他们产生的贡献相当于从 \(i\) 到 \(j\) 的连线穿过的横线的数量。
那么我们考虑状态如何设计,记 \(dp_{i,j,k}\) 表示已经匹配了前 \(i\) 行,有 \(j\) 组球与盒子未匹配,怪异度为 \(k\) 的方案数。
那么初始值为 \(dp_{0,0,0}=1\),答案为 \(dp_{n,0,m}\) 表示匹配了前 \(i\) 行,没有球与盒子未匹配,怪异度为 \(m\) 的方案数。
考虑转移,对于一行,有一个球和一个盒子,可以匹配 \(0,1,2\) 组三种可能,那么就分这三种情况进行转移。
匹配 \(0\) 组
都不匹配的话,应该是 \(dp_{i-1,j-1,k-2j}\)。
考虑第二维为什么是从 \(j-1\) 个未匹配组转移过来。
先考虑我们匹配 \(1\) 组的情况,我们新加入了 \(1\) 组,即第 \(i\) 行的球与盒子,又匹配了 \(1\) 组,那么新的没有匹配的组数没有发生变化,即第二维从 \(j\) 转移到 \(j\)。
那么匹配 \(2\) 组的情况,相比于匹配 \(1\) 组的情况多匹配了一组,所以要从 \(j + 1\) 转移到 \(j\);同理,匹配 \(0\) 组的情况就要从 \(j-1\) 转移到 \(j\)。
再考虑第三维。原本前面那些没有被匹配的盒子与球是可能被匹配到第 \(i\) 行及以后的,但是现在我们考虑的转移第 \(i\) 行并没有匹配这 \(j\) 组盒子与球。
那么这 \(j\) 组盒子与球只能匹配到第 \(i +1\) 行及以后,那么相等于我们前面的 \(j\) 组球与盒子又需要多穿过一条横线,那么总共 \(2j\) 个物品,就使得怪异值增加了 \(2j\),所以从 \(k-2j\) 转移过来。
匹配 \(1\) 组
将第 \(i\) 个球与前面的 \(i-1\) 行未被匹配的 \(j\) 个盒子进行匹配,有 \(j\) 种选择,每种选择的方案数为 \(j \times dp_{i-1,j,k-2j}\)。
用第 \(i\) 个盒子去匹配球的方案数同理。
第 \(i\) 个球连第 \(i\) 个盒子的方案数单独处理,为 \(dp_{i-1,j,k-2j}\)。
匹配 \(2\) 组
如果要匹配两组,那么第 \(i\) 行的球与盒子之间不能相互选择。
第 \(i\) 行的球与前 \(i-1\) 行的 \(j+1\) 个未匹配的盒子转移过来,盒子同理,根据乘法原理,有 \((j + 1)^2dp_{i-1,j+1,k-2j}\) 种方案。
状态转移方程
\[dp_{i,j,k}=j \times dp_{i-1,j,k-2j}+j \times dp_{i-1,j,k-2j}+dp_{i-1,j,k-2j}+(j+1)^2 \times dp_{i-1,j+1,k-2j}+dp_{i-1,j-1,k-2j} \]Code
#include <bits/stdc++.h>
using namespace std;
typedef long long MainType;
const int N = 55;
const int Mod = 1e9 + 7;
int n,m;
MainType dp[N][N][N * N];
// dp[i][j][k]
// 对于前 i 组有 j 组没有配对,怪异度为 k 的方案数
int main() {
#ifdef ONLINE_JUDGE == 1
freopen("genshin.in","r",stdin);
freopen("genshin.out","w",stdout);
#endif
cin >> n >> m;
dp[0][0][0] = 1;
for(int i = 1;i <= n; i++) {
for(int j = 0;j <= i; j++) {
for(int k = j * 2;k <= m; k++) {
if(j < 1)
dp[i][j][k] = (dp[i - 1][j + 1][k - j * 2] * (j + 1) % Mod * (j + 1) % Mod + dp[i - 1][j][k - j * 2] * (j * 2 + 1) % Mod) % Mod;
else
dp[i][j][k] = (dp[i - 1][j + 1][k - j * 2] * (j + 1) % Mod * (j + 1) % Mod + dp[i - 1][j][k - j * 2] * (j * 2 + 1) % Mod + dp[i - 1][j - 1][k - j * 2] % Mod) % Mod;
}
}
}
cout << dp[n][0][m] % Mod;
#ifdef ONLINE_JUDGE == 1
fclose(stdin);
fclose(stdout);
#endif
return 0;
}
标签:Oddness,盒子,int,转移,2j,Permutation,匹配,ABC134F,dp
From: https://www.cnblogs.com/baijian0212/p/solution-at-abc134-f.html