[ABC134F] Permutation Oddness
Judgelight
·
·
题解
[ABC134F] Permutation Oddness
题面翻译
定义一个 1 \sim n 的排列 p 的「怪异度」为
\sum_{i=1}^n|p_i-i|
求「怪异度」为 k 的 1 \sim n 的排列数，答案对 10^9+7 取模。
题解
妙妙的 DP 题，其实最难的是转化和状态设置，方程很好推。
1. 问题转化
粘了一下题面，看着清楚些
考虑转化题目，把题目中的 p_i 和 i 表示成球和盒子，球在左边摆一列，盒子在右边摆一列。如果 p_i=x，把左边的第 i 个球和右边的第 x 个盒子连起来。
如：若 p_{114514}=1919810，把左边的第 114514 个球和右边的第 1919810 个盒子连红线。
这样我们就把一个排列转化为了一个匹配数为 n 的二分图。
现在一共有 n 行，第 i 行的第一个是球，第二个是盒子，在两行之间作一根黑直线。发现每根红线（球和盒子的连线）经过的黑线数量的总和就是怪异度。
如样例 \lbrace 2,1,3 \rbrace，指 p_1=2,p_2=1,p_3=3，化为下图：
画得丑见谅 看不懂算了。
## 2. 状态设置
那这样肯定用 DP 做。
设状态 $f_{i,j,k}$ 表示前 $i$ 行，有 $j$ 组**球和盒子**没有被连线（用二分图想，这里的意思是本来应该有 $i$ 个匹配，但是只有 $i-j$ 个，剩了 $j$ 个球和 $j$ 个盒子还没有匹配），然后当前的奇异度是 $k$ 的方案数。
那么答案就是 $f_{n,0,k}$（这里 $k$ 是它输入的第二个数），表示前 $n$ 个数，匹配完了，相当于未匹配数是 $0$ ，奇异度是 $k$ 的方案数。
都看到这里了，是不是点个赞的说。
## 3. 状态转移
我们 $f_{i,j,k}$ 的方案数与 $f_{i-1,anything,anything}$ 的差距只在于第 $i$ 排的盒子和球的选择方案。可以根据这个来分类讨论，因为第 $i$ 排有两个物体，最多匹配两组，所以分类讨论匹配 $0,1,2$ 组的方案数。
#### 1. 只匹配一组
- 把第 $i$ 个球向前 $i-1$ 个盒子中未被连线的盒子连一条线，且第 $i$ 个盒子不动它的方案数，即为 $j \times f_{i-1,j,k-2j}$（乘了一个 $j$ 是因为可以选择没被选的 $j$ 个盒子中的任意一个，第二维是因为这次连了 $1$ 条边，$i$ 也多了 $1$，抵消了；第三维和下面的第三维都后面再解释，先看完分类）。
- 把第 $i$ 个盒子向前 $i-1$ 个球中未被连线的球连一条线，且第 $i$ 个球不动它的方案数，即为 $j \times f_{i-1,j,k-2j}$ （乘了一个 $j$ 是因为可以选择没被选的 $j$ 个球中的任意一个，第二维是因为这次连了 $1$ 条边，$i$ 也多了 $1$，抵消了）。
- 自己连自己的情况：单独讨论，显然是 $f_{i-1,j,k-2j}$。
#### 2. 匹配两组
- 由于要匹配两组，第 $i$ 个球和第 $i$ 个盒子显然就不能互相选了，所以选前面没被选过的就行，即 $(j+1)^2 \times f_{i-1,j+1,k-2j}$（第二维的 $j+1$，因为这次连了 $2$ 条边，$i$ 却只增加了 $1$，前面的 $(j+1)^2$ 意思就是第 $i$ 个球能选前面未被选的 $j+1$ 个盒子，第 $i$ 个盒子同理，然后这样连边是互不干扰的，所以用乘法乘起来）。
#### 3. 不匹配
- 直接就是 $f_{i-1,j+1,k-2j}$（第二维因为边数增加了 $0$， $i$ 却增加了 $1$）。
---
综上所述：
$$f_{i,j,k}=j \times f_{i-1,j,k-2j}+j \times f_{i-1,j,k-2j}+f_{i-1,j,k-2j}+(j+1)^2 \times f_{i-1,j+1,k-2j}+f_{i-1,j+1,k-2j}$$
合并同类项：
$$f_{i,j,k}=(2j+1) \times f_{i-1,j,k-2j}+(j+1)^2 \times f_{i-1,j+1,k-2j}+f_{i-1,j+1,k-2j}$$
## 4. 第三维转移的解释
比如现在有 $f_{i,j,k}$，这里的 $j$ 也有另一种表示：有 $j$ 个球和 $j$ 个盒子要连线到 $i+1 \sim n$ 中去了。
因为最后一定是有 $n$ 个匹配，这 $j$ 个球和 $j$ 个盒子又不往 $1 \sim i$ 中的元素连，那就只能往后面连了。
那么这些球和盒子连的对象行数每多 $1$，就多经过 $1$ 根黑线，奇异度就多 $1$。
本来它们是有可能连到第 $i$ 行的，结果我们把这行的连接确定了，它们的连线对象就只好整体向下移动一行了，这 $j$ 个球和 $j$ 个盒子就让奇异度多了 $j+j=2j$，算回去就是 $k-2j$。
## 5. AC Code
```cpp
#include<bits/stdc++.h>
#define int long long
#define N 59
using namespace std;
const int mod=1e9+7;
int n,magic,f[N][N][N*N];
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>magic;
f[0][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=i;j++){
for(int k=j*2;k<=magic;k++){
if(j>=1){
f[i][j][k]=(f[i-1][j-1][k-j*2]+f[i-1][j][k-j*2]*(j*2+1)%mod+f[i-1][j+1][k-j*2]*(j+1)%mod*(j+1)%mod)%mod;
}
else f[i][j][k]=(f[i-1][j][k-j*2]*(j*2+1)%mod+f[i-1][j+1][k-j*2]*(j+1)%mod*(j+1)%mod)%mod;
}
}
}
cout<<f[n][0][magic];
return 0;
}
```