P4709 信息传递 解题报告
P4709 信息传递 解题报告：
更好的阅读体验
题意
给定置换 \(f\)，求有多少个置换 \(g\) 满足 \(g^n=f\)。
\(1\leqslant |f|\leqslant 10^5\)。
分析
首先这种题一看到就把置换拆分成若干个循环置换。
对于一个循环置换 \(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。
#include
#include
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];
vectorv,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