题目大意

给定置换，求有多少个排列可以通过若干次这个置换，变成1到n的排列。

解题思路

  • 如果一个置换中没有环，如{1,2,3}，只能找出一个符合条件的原排列：{1,2,3}。
  • 如果有一个环，如{3,1,2}，由于环的长度为3（不同元素的数量），所以可以找出三种原排列：{1,2,3},[2,3,1},{3,1,2}。
  • 如果有两个环，如{2,1,4,3}，由于两个环的长度分别为2（不同元素的数量），所以可以找出两种原排列：{1,2,3,4},[2,1,4,3}。

不难得出，如果有一个长度为n的环，那么可以找出n个原序列；而有多个环的时候，可以找出这些环长度的lcm。由于长度总和就是n，所以他们的lcm一定不会大于n位，不需要取模。

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,m,l=1,t,a[100010],b[100010],v[100010],p[100010],r[100010],ans[100010];
void multi(int x)
{
    int i;
    for(i=1;i<=l;i++) ans[i]*=x;
    for(i=1;i<l;i++)
        if(ans[i]>9) ans[i+1]+=ans[i]/10,ans[i]%=10;
    while(l<n && ans[l]>9) ans[l+1]+=ans[l]/10,ans[l++]%=10;
    ans[l+1]=0;
}
int main()
{
    int x,i,j;
    ans[0]=0,ans[1]=1;
    for(i=2;i<=100000;i++)
        if(!p[i])
        {
            for(j=i*2;j<=100000;j+=i) p[j]=1;
            r[++t]=i;
        }
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
    {
        if(v[i]) continue;
        v[i]=b[++m]=1,j=a[i];
        while(j!=i) v[j]=1,b[m]++,j=a[j];
    }
    memset(p,0,sizeof(p));
    for(i=1;i<=m;i++)
        for(j=1;j<=t;j++)
        {
            if(b[i]<=1) break;
            x=0;
            while(b[i]%r[j]==0) x++,b[i]/=r[j];
            p[r[j]]=max(p[r[j]],x);
        }
    for(i=1;i<=t;i++)
        while(p[r[i]]--) multi(r[i]);
    for(i=l;i>=1;i--)
        printf("%d",ans[i]);
    return 0;
}