题解 CF1542E2【Abnormal Permutation Pairs (hard version)】

来一个非常暴力的做法。

地理学考的时候想的

看见排列还有字典序，一个显然的想法就是枚举排列 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 的生成函数显然是：

暴力乘上分子，然后除以 (x-1)^2 就相当于做两次回退背包。

时间复杂度：\mathcal{O}(n^3)。

code：

#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;
}