自动搬运

查看原文

来自洛谷，原作者为

	command_block 众水皆昂首，饮月唯我一。

搬运于2025-08-24 22:02:50，当前版本为作者最后更新于2020-10-05 14:04:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意 : 给出一个 $n$ 元置换 $f$。

求有多少个置换 $g$ 满足 $g^n=f$

$n\leq 10^5$ ,时限 $\texttt{4s}$。

有意思的题。

看到置换乘积,首先把置换分解成循环表示。

单独看一个循环,有如下定理 :

• 长度为 $m$ 的循环在 $k$ 次幂之后得到的置换有 $\gcd(k,m)$ 个等大小循环。

  可以看做每个元素转动了 $k$ 次。沿着某个环走,不断 $+k$ 再 $\bmod\ m$ ,易得恰能走 $m/\gcd(k,m)$ 步。

也就是说, $f$ 中的 $r$ 个长度为 $s$ 的环能够拼到一起当且仅当 $\gcd(rs,n)=r$。

先考虑 $r$ 个长度为 $s$ 的小环有多少中拼合的方法。

由于拼合后是大环,先钦定第一个小环的第一个元素排在第一位。

此外,其余 $r-1$ 个小环可以随意旋转,方案数为 $s^{r-1}$。

其余 $r-1$ 个小环之间还可以随意排列,方案数为 $(r-1)!$

总的来说就是 $(r-1)!s^{r-1}$。不妨设为 $p_{r,s}$。

设长度为 $i$ 的循环有 $c_i$ 个。

能够发现不同大小的循环之间互不影响,我们每种大小分开考虑。

现有 $c$ 个长度为 $s$ 的环。

设 $dp[i]$ 为使用了 $i$ 个环的方案数。

则 $dp[i]=\sum\limits_{r=1}^{i}[\gcd(rs,n)=r]\dbinom{i-1}{r-1}p_{r,s}dp[i-r]$

中间是 $\dbinom{i-1}{r-1}$ 而不是 $\dbinom{i}{r}$ 的原因 : 合成的各个环是无序的，不妨钦定每次必选第一个。

其中, $\gcd(rs,n)=r\Rightarrow r|n$ ,所以枚举量是 $O(d(n))$ 级别的。

复杂度 $O(n*d(n))$。

#include<algorithm>
#include<cstdio>
#include<vector>
#define ll long long
#define MaxN 100500
using namespace std;
const int mod=998244353;
ll powM(ll a,int t=mod-2){
  ll ret=1;
  while(t){
    if (t&1)ret=ret*a%mod;
    a=a*a%mod;t>>=1;
  }return ret;
}
int d[MaxN],tn;
ll fac[MaxN],ifac[MaxN];
ll C(int n,int m)
{return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
ll P(int r,int s)
{return fac[r-1]*powM(s,r-1)%mod;}
void Init(int n)
{
  fac[0]=1;
  for (int i=1;i<=n;i++)
    fac[i]=fac[i-1]*i%mod;
  ifac[n]=powM(fac[n])%mod;
  for (int i=n;i;i--)
    ifac[i-1]=ifac[i]*i%mod;
  for (int i=1;i<=n;i++)
    if (n%i==0)d[++tn]=i;
}
int gcd(int a,int b)
{return !b ? a : gcd(b,a%b);}
ll dp[MaxN];
ll calc(int c,int s,int n)
{
  dp[0]=1;
  for (int i=1;i<=c;i++){
    dp[i]=0;
    for (int j=1;j<=tn&&d[j]<=i;j++){
      int r=d[j];
      if (gcd(n,r*s)==r)
        dp[i]=(dp[i]+C(i-1,r-1)*P(r,s)%mod*dp[i-r])%mod;
    }
  }return dp[c];
}
bool vis[MaxN];
int n,p[MaxN],c[MaxN];
int main()
{
  scanf("%d",&n);
  Init(n);
  for (int i=1;i<=n;i++)
    scanf("%d",&p[i]);
  for (int i=1;i<=n;i++)
    if (!vis[i]){
      int siz=0,u=i;
      while(!vis[u])
        {vis[u]=1;siz++;u=p[u];}
      c[siz]++;
    }
  ll ans=1;
  for (int i=1;i<=n;i++)
    if (c[i])
      ans=ans*calc(c[i],i,n)%mod;
  printf("%lld",ans);
  return 0; 
}