题解：P10547 [THUPC2024] 排列游戏

· · 题解

先考察操作的性质。

注意到若设每个点的势能是 |i-p_i|，一次代价为 W 的操作的最多使得总势能减少 2W。因此有不等式：

Ans\ge \frac{\sum |i-p_i|}{2}

这个形式看起来就很正确。猜想其可以取到下界，所以有：

引理 1：一个排列的最小交换代价是 \dfrac{\sum |i-p_i|}{2}。

证明：

只需说明对于每个非恒等的排列有一个使总势能减少 2W 的操作即可，然后施加归纳法即可。设原排列为 p，逆排列为 r，则等价于存在：

\exists i\neq j,i\le r_j<r_i\le j

取 i 为最小的 i\neq p_i，j 为 [i,r_i] 中一个 k 使得 p_k\ge r_i 即可。这样的 i,j 总是存在的。

再考虑“交换 n 次”是什么意思。不难发现：

引理 2：可以交换 n 次到达的排列是所有奇偶性等于 n 的奇偶性的排列。

这是容易证明的：奇偶性不等于 n 的排列显然无法到达，奇偶性相等的排列可以构造：每次操作直接从后面交换即可（如果需要）。最后剩下的次数是偶数，一直操作 (1,2) 即可。

奇排列和偶排列的答案应该不会差太远，并且应该具有某种模式。打表不难发现：

引理 3：对于 \sum |i-p_i|=2k 的排列，奇偶排列的个数差的绝对值是 \binom{n-1}{k}，并且正负性是 (-1)^{n+k}。

证明（不过显然考试时这个结论是没有必要证明的）：考虑建立一个使得势能和不变的奇偶排列的映射。如果存在一个使势能和不变的交换就交换一次，这样的映射显然可逆，这样只需考虑那些不能交换的。

那些不能交换的就是循环都由连续数字构成的排列。设有 m 个循环，则势能和应该是 2(n-m)，而计数是 \binom{n-1}{m-1}=\binom{n-1}{n-m}。

这样问题就被几乎转化为 ABC134F。然后我们队在做的时候看到数据范围就不知道怎么做了。

事实上这里的 DP 就是采取 ABC134F 的方法。比如这一篇题解。但是那道题的时间复杂度是 O(n^2m)，似乎难以通过。

但是本题具有更特殊的性质：m 量级小于 n^2。仔细分析这篇题解的状态，应该有 j（第二维）是 O(\sqrt m) 的，只是由于那道题的 m=n^2 才没有改变复杂度。

这样最后的复杂度就是 O(nm\sqrt m)，可以通过。

注：代码里的状态实际上是官方题解的状态，也就是说这个代码的 j（代码里是 d+i）是上面那篇题解的 i-j。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int T,n,m,N=500,M=10000,SM=80;
int f[2][160][10005],fac[100005],ifac[10005];
int qp(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
inline int C(int a,int b){
    if(b>a)return 0;
    return fac[a]*ifac[b]%mod*ifac[a-b]%mod;
}
int s[505][20005];
inline int pow1(int x){
    if(x&1)return mod-1;
    return 1;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    fac[0]=1;
    for(int i=1;i<=M;i++)fac[i]=fac[i-1]*i%mod;
    ifac[M]=qp(fac[M],mod-2);
    for(int i=M-1;i>=0;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
    int I2=(mod+1)/2,cur=0;
    f[cur][0][0]=1;
    for(int i=1;i<=N;i++){
        cur^=1;
        for(int d=0;d<=min(SM,i);d++){
            for(int k=(d-1)*d;k<=M;k+=2){
                f[cur][d][k]=0;
                if(d>0)f[cur][d][k]=f[cur^1][d-1][k-2*(d-1)];
                if(k>=2*d)f[cur][d][k]+=f[cur^1][d][k-2*d]*(2*d+1);
                if(f[cur][d][k]>=mod)f[cur][d][k]-=mod;
                if(k>=2*(d+1))(f[cur][d][k]+=f[cur^1][d+1][k-2*(d+1)]*(d+1)*(d+1))%=mod;
            }
        } 
        for(int j=0;j<=M;j++){
            if(j&1)continue;
            int k=j/2,F=f[cur][0][j];
            if(k<=i)(F+=pow1((i&1)+(k&1))*C(i-1,k)%mod)%=mod;
            F=F*I2%mod;
            s[i][j]=((j>0?s[i][j-2]:0)+F)%mod;
        }
    }
    cin>>T;
    while(T--){
        cin>>n>>m;
        int ans=s[n][m*2];
        cout<<ans<<endl;
    }
    return 0;
}