Submission #1798847

---

Source Code Expand

#include<cstdio>
#define ll long long
#define mod 1000000007
#define N 110000
inline char gc(){
	static char now[1<<16],*S,*T;
	if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
	return *S++;
}
inline int read(){
	int x=0;char ch=gc();
	while (ch<'0'||ch>'9') ch=gc();
	while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();}
	return x;
}
int a[N],in[N],color[N],mark[N],cnt[N],n,foot[N];bool circle[N];
ll dp[N];
int main(){
	//freopen("agc.in","r",stdin);
	n=read();ll ans=1;
	for (int i=1;i<=n;++i) a[i]=read(),++in[a[i]];
	for (int i=1;i<=n;++i){
		if (color[i]) continue;int x=i;
		for(;!color[x];x=a[x]) color[x]=i;
		if (color[x]!=i) continue;
		for (;!circle[x];x=a[x]) circle[x]=1; 
	}
	for (int i=1;i<=n;++i) if ((circle[i]&&in[i]>2)||(!circle[i]&&in[i]>1)) {printf("0");return 0;}
	//处理痞老板(基环内向树） 
	for (int i=1;i<=n;++i){
		if (in[i]) continue;int x=i,tmp=0;
		while(!circle[x]) x=a[x],tmp++;foot[x]=tmp;
	} 
	for (int i=1;i<=n;++i){
		if (!circle[i]) continue;int x=i,st=0,first=0,id=0,len=0;
		while (circle[x]){
			++id;circle[x]=0;
			if (foot[x]){
				if (!first){
					st=first=id;len=foot[x];x=a[x];continue;
				}else{
					int numm=(foot[x]<(id-st))+(foot[x]<=(id-st));
					(ans*=numm)%=mod;if (!ans) {printf("0");return 0;}st=id;x=a[x];continue;
				}
			}x=a[x];
		}if (first){
			int numm=(len<(id+first-st))+(len<=(id+first-st));
			(ans*=numm)%=mod;if (!ans) {printf("0");return 0;}
		}else cnt[id]++;
	}
	//for (int i=1;i<=n;++i) if (cnt[i]) printf("%d %d\n",i,cnt[i]);
	for (int i=1;i<=n;++i){
		dp[0]=1;if (!cnt[i]) continue;
		if (i>1&&(i%2)){
			for (int j=1;j<=cnt[i];++j) {
				dp[j]=dp[j-1]*2%mod;if (j>1) (dp[j]+=dp[j-2]*(j-1)*i%mod)%=mod;
			}
		}else{
			for (int j=1;j<=cnt[i];++j){
				dp[j]=dp[j-1];if (j>1) (dp[j]+=dp[j-2]*(j-1)*i%mod)%=mod;
			}	
		}
		(ans*=dp[cnt[i]])%=mod;if (!ans){printf("0");return 0;}
	}printf("%lld",ans);
	return 0;
}

Submission Info

Judge Result