P10547 [THUPC 2024 决赛] 排列游戏 题解

· · 题解

设格子 i 上的卡片为 p_i。

性质：排列 p 被还原所需时间为 \dfrac 1 2\sum\limits_{i=1}^n |p_i-i|。

证明：显然 \dfrac 1 2\sum\limits_{i=1}^n |p_i-i| 是下界，而任意时刻一定存在 (i,j) 满足交换 i,j 带来的贡献是满的，因此 \dfrac 1 2\sum\limits_{i=1}^n |p_i-i| 可以取到。

于是，能够用不超过 m 的总时间还原的限制，可以转化为 \sum\limits_{i=1}^n |p_i-i| \le 2m。

性质：\sum\limits_{i=1}^n |p_i-i|=2\sum\limits_{i=1}^n [p_i \gt i](p_i-i)

证明：显然一个环中上升的边的长度之和与下降的边的长度之和相等，即 \sum\limits_{i=1}^n [p_i \gt i](p_i-i)=\sum\limits_{i=1}^n [p_i \lt i](p_i-i)，而左式与右式之和等于 \sum\limits_{i=1}^n |p_i-i|，因此原式成立。

于是，\sum\limits_{i=1}^n |p_i-i| \le 2m 可以转化为 \sum\limits_{i=1}^n [p_i \gt i](p_i-i) \le m。

性质：排列 p 是通过 n 次交换操作生成的，等价于排列 p 的置换环数量为偶数。

证明：初始时排列 p 的置换环数量的奇偶性与 n 的奇偶性相同，而每次交换操作都会使排列 p 的置换环数量改变 1，因此 n 次交换操作结束后排列 p 的置换环数量为偶数。

于是问题变成了，对 \sum\limits_{i=1}^n [p_i \gt i](p_i-i) \le m 且置换环数量为偶数的排列 p 计数。

考虑把每一对 (i,p_i) 看成从 i 到 p_i 的有向边，从小到大加入每一个 p_w。设 f_{i,j,k,x} 表示，考虑到 p_w=i，目前有 j 条链，总贡献为 k，且置换环数量奇偶性为 x 的方案数。把 (p_i-i) 的贡献拆到每一段 [v,v+1] 上，设 k'=k+j，转移考虑分类讨论：

初始化 f_{0,0,0,0}=1，答案即为 \sum\limits_{k=0}^m f_{n,0,k,0}。

性质：第二维是 \mathcal O(\sqrt m) 的。

证明：如果第二维的值超过了 \sqrt m，就算每次都合并一条链，均摊下来每条链也会造成至少 \sqrt m 的贡献，导致总贡献超过 m。

于是总时间复杂度为 \mathcal O(Tm+nm\sqrt m)。由于空间限制比较紧，需要使用滚动数组优化，并将所有询问离线处理。

const int N=505,M=5005,S=72,mod=1e9+7;
int T,n,m,f[2][S][M][2],ans[M];
vector <pii> ve[N];
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>T;
    for(int i=1;i<=T;i++) cin>>n>>m,ve[n].pb({m,i});
    n=500,m=5000,f[0][0][0][0]=1;
    for(int i=1;i<=n;i++){
        int ii=i&1;
        memset(f[ii],0,sizeof f[ii]);
        for(int j=0;j<min(i,S);j++){
            for(int k=0,kk=j;kk<=m;k++,kk++){
                for(int x=0;x<2;x++){
                    if(!f[ii^1][j][k][x]) continue;
                    if(j+1<S) add(f[ii][j+1][kk][x],f[ii^1][j][k][x]);
                    add(f[ii][j][kk][1-x],f[ii^1][j][k][x]);
                    add(f[ii][j][kk][x],2ll*j*f[ii^1][j][k][x]%mod);
                    if(j) add(f[ii][j-1][kk][x],1ll*j*(j-1)*f[ii^1][j][k][x]%mod);
                    if(j) add(f[ii][j-1][kk][1-x],1ll*j*f[ii^1][j][k][x]%mod);
                }
            }
        }
        for(auto p:ve[i]) for(int k=0;k<=p.fi;k++) add(ans[p.se],f[ii][0][k][0]);
    }
    for(int i=1;i<=T;i++) cout<<ans[i]<<endl;
}