CF1542E2 Abnormal Permutation Pairs (hard version)
CF1542E2 Abnormal Permutation Pairs (hard version)
good tea。
对于两个排列 \(p,q\)，如果 \(p\) 的字典序小于 \(q\)，则要么 \(p_1
首先，我们可以枚举 \(p_1\) 和 \(q_1\)，这样可以消除字典序的限制。它们对逆序对的贡献就分别为 \(p_1-1\) 和 \(q_1-1\)。如果再枚举 \(q_{2\sim n}\) 的逆序对个数 \(y\)，那么符合限制的 \(p_{2\sim n}\) 的逆序对个数 \(x\) 应该满足 \(x+p_1-1>y+q_1-1\)。即 \(x>y+q_1-p_1\)。
根据上面的要求，我们设计 DP：设 \(f_{i,j}\) 为长度为 \(i\)，逆序对数量为 \(j\) 的排列个数。转移方程很简单，因为从 \(i-1\to i\) 时只需要考虑 \(i\) 放在哪里：如果它放在倒数第 \(k\) 位，那么它对逆序对个数的贡献就是 \(k-1\)。因此转移方程为 \(f_{i,j}=\sum_{k=\max(0,j-i+1)}^jf_{i-1,k}\)，显然可以前缀和优化到 \(n^3\)。
求出 \(f\) 后可以计算答案长度为排列长度为 \(n\) 时的答案了：记 \(s_{i,j}=\sum_{k=1}^j f_{i,k}\)，\(m=\binom{n-1}{2}\)，则答案为 \(\sum_{p_1=1}^{n-1}\sum_{q_1=p_1+1}^n\sum_{y=0}^{m-(q_1-p_1)}f_{n,y}\times(s_{n,m}-s_{n,y+q_1-p_1})\)。该部分时间复杂度为 \(n^4\)，则总时间复杂度 \(n^5\)，显然无法承受。
注意到我们不关系 \(p_1,q_1\) 的具体值，只关心 \(q_1-p_1\)，因此可以枚举 \(d=q_1-p_1\)，那么使 \(q_1-p_1=d\) 的 \(q_1,p_1\) 一共有 \(n-d\) 种情况。上述柿子变为 \(\sum_{d=1}^{n-1}\sum_{y=0}^{m-d}f_{n,y}\times (s_{n,m}-s_{n,y+d})\times (n-d)\)。总时间复杂度为 \(n^4\)，还是无法承受。
那么继续拆柿子！此时我们只枚举 \(y\) 对于特定的 \(y\)，\(f_{n,y}s_{n,m}(n-d)\) 显然可以把与 \(d\) 无关的 \(f_{n,y}s_{n,m}\) 用乘法分配律提出，那么因为 \(d\) 的上界为 \(t=\min(i-1,m-y)\)，所以 \(\sum_{d=1}^t(n-d)\) 显然可以用等差数列求和公式快速求出，即为 \(\frac{(2n-1-t)t}{2}\)。
剩下来的 \(-f_{n,y}s_{n,y+d}(n-d)\) 似乎有些棘手。没关系，先把与 \(d\) 无关的 \(-f_{n,y}\) 提出，注意到 \(s_{n,y+d}(n-d)\) 中的 \(s_{n,y+d}\) 随着 \(d\) 的递增，其前面的系数是递减的。老套路了：把 \(n-d\) 拆成 \((n+y)-(y+d)\)。\(-s_{n,y+d}(y+d)\) 显然可以前缀和 \(sk_{n,j}=-\sum_{k=1}^js_{n,k}\times k\) 预处理出来；\(s_{n,y+d}(n-y)\) 把 \(n-y\) 提出来，预处理 \(s\) 的前缀和即可。
时间复杂度 \(n^3\)。代码中 \(y\) 的枚举上界是 \(m-d-1\) 而不是 \(m-d\)，因为 \(y=m-d\) 时 \(s_{n,m}-s_{n,y+d}=s_{n,m}-s_{n,m}=0\)，对答案无影响。代码中的 \(r\) 即为计算 \(-f_{n,y}s_{n,y+d}(n-d)\) 时 \(y+d\) 的上界。
#include
using namespace std;
const int N=505;
int n,mod,ans,f[N][N*N/2],s[N][N*N/2],pp[N*N/2],ss[N*N/2];
int main(){
cin>>n>>mod,f[1][0]=s[1][0]=s[1][1]=1;
for(int i=2;i<=n;i++){
for(int j=0;j<=i*(i-1)/2;j++){
f[i][j]=(s[i-1][j]-(j