题解 P4709【信息传递】
whiteqwq
·
·
题解
P4709 信息传递 解题报告：
更好的阅读体验
题意
给定置换 f，求有多少个置换 g 满足 g^n=f。
## 分析
首先这种题一看到就把置换拆分成若干个循环置换。
对于一个循环置换 $g$，我们考虑它的 $n$ 次方的形态：应该是 $\gcd(|g|,n)$ 个相同的循环，那么等价地，$a$ 个大小为 $b$ 的循环能够拼起来当且仅当 $\gcd(ab,n)=a$。
由于我们得到的是最终的循环置换，所以我们考虑把若干个大小相同的循环拼起来，我们仅需要对于每个环大小计算其贡献然后乘起来就好了。
我们考虑 $a$ 个大小为 $b$ 的环拼起来有多少种方法，由于是环首先要钦定一个位置作为开始，不妨令其为第一个环的第一个位置，而由于其他环需要断环为链，且内部要进行排列，所以一共会有 $(a-1)!b^{a-1}$ 种方案。
我们设一共有 $k$ 个大小为 $b$ 的环，设 $f_i$ 表示用了 $k$ 个环的代价，可以列出转移方程：
$$f_i\leftarrow\sum_{d=1}^i[\gcd(b\times d,n)=d](d-1)!b^{d-1}{i-1\choose d-1}f_{i-r}$$
注意这里是 ${i-1\choose d-1}$ 是因为若干次选择之间是无序的，所以我们需要钦定一个环为第一个选的才能去重。
枚举 $d$ 可以只枚举 $n$ 的因子，最终复杂度为 $O(nd(n)+\sqrt{n}d(n)\log n)$。
## 代码
目前是最优解 rk1。
```cpp
#include<stdio.h>
#include<vector>
using namespace std;
const int maxn=100005,mod=998244353;
int n,ans;
int p[maxn],vis[maxn],tot[maxn],f[maxn],fac[maxn],inv[maxn],nfac[maxn],mul[maxn];
vector<int>v,d;
int gcd(int a,int b){
return b==0? a:gcd(b,a%b);
}
int solve(int a,int b){
f[0]=mul[0]=1;
for(int i=1;i<=a;i++)
mul[i]=1ll*mul[i-1]*b%mod;
d.clear();
for(int i=0;i<v.size()&&v[i]<=a;i++)
if(gcd(b*v[i],n)==v[i])
d.push_back(v[i]);
for(int i=1;i<=a;i++){
f[i]=0;
for(int j=0;j<d.size()&&d[j]<=i;j++)
f[i]=(f[i]+1ll*mul[d[j]-1]*f[i-d[j]])%mod;
f[i]=1ll*f[i]*inv[i]%mod;
}
return 1ll*f[a]*fac[a]%mod;
}
int main(){
scanf("%d",&n);
fac[0]=nfac[0]=1;
for(int i=1;i<=n;i++)
fac[i]=1ll*fac[i-1]*i%mod,inv[i]=i==1? 1:(mod-1ll*(mod/i)*inv[mod%i]%mod),nfac[i]=1ll*nfac[i-1]*inv[i]%mod;
for(int i=1;i<=n;i++)
scanf("%d",&p[i]);
for(int i=1;i<=n;i++)
if(vis[i]==0){
int cnt=0;
for(int j=i;vis[j]==0;j=p[j])
vis[j]=1,cnt++;
tot[cnt]++;
}
for(int i=1;i<=n;i++)
if(n%i==0)
v.push_back(i);
ans=1;
for(int i=1;i<=n;i++)
if(tot[i])
ans=1ll*ans*solve(tot[i],i)%mod;
printf("%d\n",ans);
return 0;
}
```