自动搬运

查看原文

来自洛谷，原作者为

	qczrz6v4nhp6u Tell me, what scares you.

搬运于2025-08-24 23:05:47，当前版本为作者最后更新于2024-11-08 08:25:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

若干年前刚学 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)$ 即为：

$$\begin{aligned} 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;
}