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

DerrickLo · 2024-11-11 14:02:18 · 题解

我们考虑一个大小为 m 的置换环如果进行了 k 次操作，那么显然每个数都变成了这个数在置换环上后面的第 k 个数，此时这个置换环会分成 \gcd(m,k) 个新的大小为 \dfrac{m}{\gcd(m,k)} 的置换环。

那么对于原排列的每个置换环，最终都会分成若干个等大小的置换环。设操作完的排列中大小为 i 的置换环有 a_i 个，那么记 f_{i,j} 表示有 j 个大小为 i 的置换环时，它们能拼成原图置换环的方式数，那么答案就是 \displaystyle \prod_{i=1}^{n}f_{i,a_i}。

接下来问题就变成了怎么求 f_{i,j}，考虑转移时枚举 x 表示此时第 1 个置换环在原图中在一个 i\times x 的大置换环中，这里的 x 需要满足 \gcd(k,i\times x)=x。那么对于这个大置换环内部排列的方案数，不难发现对于每个小置换环有 i 种排列方式，而这些小置换环之间有 x! 种排列方式，而由于是一个环，所以还要除以 i\times x，也就是说方案数是 \dfrac{i^x\times x!}{i\times x}。

那么不难列出转移方程：

直接暴力转移即可。时间复杂度 \mathcal O(Tnd(k)\log k)。

#include<bits/stdc++.h>
#define mod 998244353
#define int long long
using namespace std;
int t,n,m,p[3005],f[3005],fac[3005],inv[3005],invv[1000005],vis[3005],cnt[3005];
vector<int>d;
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod,b>>=1;
    }
    return res;
}
int C(int n,int m){
    if(n<m)return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t,fac[0]=1;
    for(int i=1;i<=3000;i++)fac[i]=fac[i-1]*i%mod,invv[i]=ksm(i,mod-2);
    inv[3000]=ksm(fac[3000],mod-2);
    for(int i=2999;~i;i--)inv[i]=inv[i+1]*(i+1)%mod;
    while(t--){
        cin>>n>>m,d.clear();
        for(int i=1;i<=n;i++)cin>>p[i],vis[i]=0,cnt[i]=0;
        for(int i=1;i<=m;i++)if(m%i==0)d.emplace_back(i);
        for(int i=1;i<=n;i++)if(!vis[i]){
            int now=i,cntt=0;
            while(!vis[now])vis[now]=1,cntt++,now=p[now];
            cnt[cntt]++;
        }
        int ans=1;
        for(int i=1;i<=n;i++){
            f[0]=1;
            for(int j=1;j<=cnt[i];j++)f[j]=0;
            for(int j=1;j<=cnt[i];j++)for(int k:d)if(k<=j&&__gcd(m/k,i)==1)f[j]+=C(j-1,k-1)*f[j-k]%mod*ksm(i,k)%mod*fac[k]%mod*invv[i*k]%mod,f[j]%=mod;
            ans*=f[cnt[i]],ans%=mod;
        }
        cout<<ans<<"\n";
    }
    return 0;
}