题解 P4709 【信息传递】

· · 题解

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

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

------------ 有意思的题。 看到置换乘积,首先把置换分解成循环表示。 单独看一个循环,有如下定理 : - 长度为 $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; 
}