题解：P11256 [GDKOI2023 普及组] 置换

· · 题解

若干年前刚学 OI，看到这个题一点思路都没有，但是现在看来似乎并没有那么困难。

Solution

对于每个置换环考虑。设 r_1 为 Y 上的一个置换环，r_2 为 X 上该置换环所在的置换环。那么应该有：

|r_2|=|r_1|\times \gcd(k,|r_2|)

解释一下：\gcd(k,|r_2|) 是 r_1 对应到 r_2 上相邻两个点之间的距离，乘上点数即为环长。

通过这个可以得到 r_2 上应该有恰好 \gcd(k,|r_2|) 个长度为 |r_1| 的环。

对每种长度的置换环分别考虑，最后再将答案乘起来。将 \frac{|r_2|}{|r_1|} 个长度为 |r_1| 的置换环分配到一个长度为 |r_2| 的置换环的方案数即为

(\frac{|r_2|}{|r_1|}-1)!\times |r_1|^{\frac{|r_2|}{|r_1|}-1}

即钦定一个置换环不动，其他置换环乱放的方案数。

考虑其关于 |r_2| 的 EGF。设 p=|r_1|，l=|r_2|，c=\frac{l}{p}，g=(c-1)!\times p^{c-1}，则关于 l 的 EGF F_l(z) 即为：

F_l(z)&=\sum_{n\ge 0}[c|n]\frac{n!}{(c!)^{\frac nc}(\frac{n}{c})!}\times g^{\frac nc}\times \frac{z^n}{n!}\\ &=\sum_{n\ge 0}\frac{1}{(c!)^nn!}\times g^n\times z^{nc}\\ &=\sum_{n\ge 0}\frac{(\frac{gz^c}{c!})^n}{n!} \end{aligned}

设 S 为 l=|r_1|\times \gcd(k,l) 满足条件的 l 的集合，m 为长度为 |r_1| 的置换环的数量，则答案即为

m![z^m]\prod_{l\in S}F_l(z)

直接暴力把这个东西卷起来就是 O(n^2\ln n) 的，而且严重跑不满。

考虑进一步优化。注意到 F_l(z)=\exp(\frac{gz^c}{c!})，则答案的 EGF 即为

\prod_{l\in S}F_l(z)=\exp(\sum_{l\in S}\frac{gz^c}{c!})

暴力算这个东西可以做到 O(n^2)，使用多项式科技可以做到 O(n\log^2 n) 或 O(n\log n)。

Code

一个 O(n^2\ln n) 的实现。

#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=3005,mod=998244353;
int n,m,a[N],cnt[N];
bool vis[N];
vector<int> dvs;
ll fac[N],ifac[N];
inline ll qpow(ll a,ll b){
    ll res=1;
    for(;b;b>>=1,a=a*a%mod)
        if(b&1)res=res*a%mod;
    return res;
}
ll f[N];
ll dp(int len,int n){
    for(int i=0;i<=n;i++)f[i]=0;
    f[0]=1;
    for(auto &c:dvs){
        if(c>n)break;
        if(__gcd(m,len*c)==c){
            ll g=fac[c-1]*qpow(len,c-1)%mod*ifac[c]%mod;
            for(int i=n;i>=0;i--){
                ll cur=g;
                for(int k=1;c*k<=i;k++,cur=cur*g%mod)
                    f[i]=(f[i]+f[i-c*k]*cur%mod*ifac[k])%mod;
            }
        }
    }
    return f[n]*fac[n]%mod;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    fac[0]=1;
    for(int i=1;i<=3000;i++)fac[i]=fac[i-1]*i%mod;
    ifac[3000]=qpow(fac[3000],mod-2);
    for(int i=3000;i>=1;i--)ifac[i-1]=ifac[i]*i%mod;
    int _Test;cin>>_Test;
    while(_Test--){
        cin>>n>>m;
        dvs.clear();
        for(int i=1;i<=m;i++)
            if(m%i==0)
                dvs.emplace_back(i);
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cnt[i]=vis[i]=0;
        for(int i=1;i<=n;i++){
            int len=0;
            for(int x=i;!vis[x];x=a[x])vis[x]=1,++len;
            ++cnt[len];
        }
        ll ans=1;
        for(int i=1;i<=n;i++)
            ans=ans*dp(i,cnt[i])%mod;
        cout<<ans<<'\n';
    }
    return 0;
}