Submission #3245319

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int mod=1e9+7;
int gi() {
    int x=0,o=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
int n,ans=1,a[N],du[N],pre[N],cnt[N],f[N];
bool vis[N];
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=gi(),du[a[i]]++;
    for(int i=1;i<=n;i++) {
        if(du[i]>2) return puts("0"),0;
        if(du[i]<2||vis[i]) continue;
        int p=i;
        do {
            if(vis[p]) return puts("0"),0;
            vis[p]=1;pre[a[p]]=p;p=a[p];
        } while(p!=i);
    }
    for(int i=1;i<=n;i++)
        if(!du[i]) {
            int p=i,l1=0,l2=0;
            while(!vis[p]) vis[p]=1,p=a[p],l1++;
            do l2++,p=pre[p]; while(du[p]!=2);
            if(l1<l2) ans=2ll*ans%mod;
            else if(l1>l2) return puts("0"),0;
        }
    for(int i=1;i<=n;i++)
        if(!vis[i]) {
            int p=i,l=0;
            do p=a[p],l++,vis[p]=1; while(p!=i);
            cnt[l]++;
        }
    for(int i=1;i<=n;i++) {
        int mul=1;if(i!=1&&(i&1)) mul++;
        f[0]=1;f[1]=mul;
        for(int j=2;j<=cnt[i];j++) f[j]=(1ll*f[j-2]*(j-1)%mod*i%mod+1ll*f[j-1]*mul%mod)%mod;
        ans=1ll*ans*f[cnt[i]]%mod;
    }
    printf("%d\n",ans);
    return 0;
}

Submission Info

Judge Result