Submission #1695294

---

Source Code Expand

#include<bits/stdc++.h>
#define N 100005
#define ll long long
#define P 1000000007
using namespace std;
int n,fa[N],b[N],rd[N],fl[N],sum[N];
void biu()
{
	puts("0");
	exit(0);
}
void dfs(int x)
{
	if (fl[fa[x]]) biu();
	rd[fa[x]]--;fl[fa[x]]=fl[x]+1;rd[x]=-1;
	if (rd[fa[x]]==0) dfs(fa[x]);
}
int F(int x,int k)
{
	static int f[N];
	f[0]=1;f[1]=2;
	for (int i=2;i<=x;i++)
		f[i]=(f[i-1]*2+(ll)f[i-2]*(i-1)%P*k)%P;
	return f[x];
}
int G(int x,int k)
{
//	cout<<x<<' '<<k<<endl;
	static int g[N];
	g[0]=1;g[1]=1;
	for (int i=2;i<=x;i++)
		g[i]=(g[i-1]+(ll)g[i-2]*(i-1)%P*k)%P;
	return g[x];
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&fa[i]),rd[fa[i]]++;
	for (int i=1;i<=n;i++)
		if (rd[i]==0) dfs(i);
	int Ans=1;
	for (int i=1;i<=n;i++)
		if (rd[i]==1)
		{
			int x=i,y=fa[i],cnt=0,flag=0;
			b[++cnt]=fl[i];
			if (fl[i]) flag=cnt;
			for (;y!=i;y=fa[y],x=fa[x])
			{
				b[++cnt]=fl[y];rd[y]=0;
				if (fl[y]) flag=cnt;
			}
			//cout<<cnt<<' '<<flag<<endl;
			if (!flag) sum[cnt]++;
			else
			{
				flag=flag-cnt;
				for (int j=1;j<=cnt;j++)
				{
					//cout<<b[j]<<endl;
					if (b[j])
					{
						if (b[j]>j-flag) biu();
						if (b[j]<j-flag) Ans=Ans*2%P;
						flag=j;
					}
				}
			}
		}
	//	cout<<Ans<<endl;
	for (int i=1;i<=n;i++)
	{
	//	cout<<i<<' '<<sum[i]<<endl;
		if ((i&1)&&i!=1) Ans=(ll)Ans*F(sum[i],i)%P;
		else Ans=(ll)Ans*G(sum[i],i)%P;
	}
	printf("%d\n",Ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:37:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:39:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&fa[i]),rd[fa[i]]++;
                                 ^

Judge Result