题解 CF1542E2【Abnormal Permutation Pairs (hard version)】
Froggy
2021-07-04 13:56:15
来一个非常暴力的做法。
~~地理学考的时候想的~~
---
看见排列还有字典序，一个显然的想法就是枚举排列 $p$ 和 $q$ 的最长公共前缀。
假设最长公共前缀是 $i$，那么再枚举 $p_{i+1}$ 和 $q_{i+1}$ 的值，满足 $p_{i+1}<q_{i+1}$，那么后面的就可以随便填了，后面可以看成是长度为 $n-i-1$ 的排列。
分别设 $p_{i+1}$ 和 $q_{i+1}$ 在最后 $n-i$ 个数的排名（从小到大排）是 $a$ 和 $b$；分别设 $p$ 和 $q$ 最后 $n-i-1$ 个数的逆序对数是 $t_p$ 和 $t_q$。
由于 $p$ 和 $q$ 前 $i$ 个数全一样，所以显然需要满足 $a+t_p>b+t_q$，即 $t_p-t_q\geq b-a+1$。
那么现在的问题就变成了求有多少对长度为 $n-i-1$ 的排列满足两个排列的逆序对的差为 $j$ $\ (j\in [1,n-i+1])$ 的方案数。
从小到大一个一个插到排列里，直接暴力 dp 是 $\mathcal{O}(n^4)$ 或者 $\mathcal{O}(n^5)$ 的。不妨考虑把生成函数写出来。
插入 $i$ 的生成函数显然是：
$$\begin{aligned}
&\left(\sum\limits_{j=0}^{i-1}x^j\right)\left(\sum\limits_{j=0}^{i-1}x^{-j}\right) \\
=& \frac{x^i-1}{x-1}\cdot\frac{x^{-i}-1}{x^{-1}-1} \\
=& \frac{x^{i+1}+x^{-i+1}-2x}{(x-1)^2}
\end{aligned}$$
暴力乘上分子，然后除以 $(x-1)^2$ 就相当于做两次回退背包。
时间复杂度：$\mathcal{O}(n^3)$。
***code：***
```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 505
typedef long long ll;
const int B=251*501;
int n,mod,dp[2][N*N],ans,A[N];
int main(){
n=read(),mod=read();
A[0]=1;
for(int i=1;i<=n;++i){
A[i]=1LL*A[i-1]*(n-i+1)%mod;
}
dp[0][B]=1;
#define update(x,y) x=(x+y)%mod
for(int i=1;i<n;++i){
memset(dp[i&1],0,sizeof(dp[i&1]));
int C=(i+1)*(i+1)/2;
for(int j=B-C;j<=B+C;++j){
int w=dp[(i-1)&1][j];
if(w){
update(dp[i&1][j+i+1],w);
update(dp[i&1][j-i+1],w);
update(dp[i&1][j+1],1LL*(mod-2)*w);
}
}
int zyk=2;
while(zyk--){
for(int j=B+C;j>=B-C;--j){
update(dp[i&1][j],dp[i&1][j+1]);
}
for(int j=B-C;j<=B+C;++j)dp[i&1][j]=dp[i&1][j+1];
}
static int suf[N*N];
for(int j=C;j>=0;--j){
suf[j]=(suf[j+1]+dp[i&1][B+j])%mod;
}
for(int a=0;a<=i;++a){
for(int b=a+1;b<=i;++b){
update(ans,1LL*A[n-i-1]*suf[b-a+1]);
}
}
}
printf("%d\n",ans);
return 0;
}
```