Submission #1799723
Source Code Expand
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
#define repd(i,x,y) for (int i=x; i>=y; --i)
using namespace std;
typedef long long LL;
const int p=1000000007;
int n,a[100100],in[100100],cnt[100100],ans,fac[100100],inv[100100],len[100100],flag[100100],clk;
bool cyc[100100];
struct edge
{
int v;
edge *nxt;
} pool[100100],*tp=pool,*fst[100100];
int getint()
{
char ch;
while (!isdigit(ch=getchar()));
int x=ch-'0';
for (; isdigit(ch=getchar()); x=x*10+ch-'0');
return x;
}
int power(int x,int k)
{
int ret=1;
for (; k; k>>=1,x=LL(x)*x%p)
if (k&1)
ret=LL(ret)*x%p;
return ret;
}
int calc(int n,int m)
{
return LL(fac[n])*inv[m]%p*inv[n-m]%p;
}
int get(int x)
{
if (in[x]==1)
return 0;
int ret=1;
x=cyc[fst[x]->v]?fst[x]->nxt->v:fst[x]->v;
for (; fst[x]; x=fst[x]->v,++ret)
if (in[x]>1)
{
puts("0");
exit(0);
}
return ret;
}
int dp(int n)
{
static int f[100100],sum[100100];
memset(f,0,sizeof(int)*(n+10)),f[n+1]=1,len[n+1]=len[1];
repu(i,1,n)
sum[i]=sum[i-1]+len[i];
if (!sum[n])
return 1+(n&1);
repd(i,n+1,2)
if (len[i])
{
if (i-len[i] && !(sum[i-1]-sum[i-len[i]]))
(f[i-len[i]]+=f[i])%=p;
if (i-len[i]-1 && !(sum[i-1]-sum[i-len[i]-1]))
(f[i-len[i]-1]+=f[i])%=p;
}
else
(f[i-1]+=f[i])%=p;
return f[1];
}
int main()
{
n=getint(),ans=1;
repu(i,1,n)
{
if (++in[a[i]=getint()]>2)
{
puts("0");
return 0;
}
*tp=(edge){i,fst[a[i]]},fst[a[i]]=tp++;
}
repu(i,1,n)
if (!in[i])
{
int j=i,tot;
for (++clk; !flag[j]; flag[j]=clk,j=a[j]);
if (flag[j]!=clk)
{
if (!cyc[j])
{
puts("0");
return 0;
}
continue;
}
for (; !cyc[j]; cyc[j]=1,j=a[j]);
len[tot=1]=get(j);
for (int k=a[j]; k!=j; len[++tot]=get(k),k=a[k]);
ans=LL(ans)*dp(tot)%p;
}
repu(i,1,n)
if (!flag[i])
{
int tot=0;
for (int j=i; !flag[j]; flag[j]=1,j=a[j],++tot);
++cnt[tot];
}
fac[0]=fac[1]=inv[0]=inv[1]=1;
repu(i,2,n)
inv[i]=LL(p-p/i)*inv[p%i]%p;
repu(i,2,n)
{
fac[i]=LL(fac[i-1])*i%p;
inv[i]=LL(inv[i-1])*inv[i]%p;
}
memset(len,0,sizeof(len));
repu(i,1,n)
if (cnt[i])
{
int w=dp(i),sum=0,t=1;
repu(j,0,cnt[i]/2)
{
sum=(sum+LL(t)*calc(cnt[i],j*2)%p*power(i,j)%p*power(w,cnt[i]-j*2))%p;
t=LL(j*2+1)*t%p;
}
ans=LL(ans)*sum%p;
}
printf("%d\n",ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Next or Nextnext |
User |
dwjshift |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3154 Byte |
Status |
WA |
Exec Time |
17 ms |
Memory |
5760 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 1400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
WA |
1 ms |
2176 KB |
0_01.txt |
AC |
1 ms |
2176 KB |
0_02.txt |
AC |
1 ms |
2176 KB |
0_03.txt |
AC |
1 ms |
2176 KB |
0_04.txt |
AC |
1 ms |
2176 KB |
1_00.txt |
WA |
1 ms |
2176 KB |
1_01.txt |
WA |
17 ms |
4992 KB |
1_02.txt |
AC |
13 ms |
4992 KB |
1_03.txt |
AC |
12 ms |
4992 KB |
1_04.txt |
AC |
11 ms |
5248 KB |
1_05.txt |
AC |
11 ms |
5376 KB |
1_06.txt |
AC |
11 ms |
5760 KB |
1_07.txt |
WA |
11 ms |
4992 KB |
1_08.txt |
AC |
14 ms |
5760 KB |
1_09.txt |
AC |
6 ms |
4736 KB |
1_10.txt |
AC |
14 ms |
5760 KB |
1_11.txt |
AC |
10 ms |
4992 KB |
1_12.txt |
AC |
14 ms |
5376 KB |
1_13.txt |
AC |
14 ms |
5376 KB |
1_14.txt |
AC |
14 ms |
5376 KB |
1_15.txt |
AC |
14 ms |
5504 KB |
1_16.txt |
AC |
14 ms |
5504 KB |
1_17.txt |
AC |
14 ms |
5504 KB |
1_18.txt |
AC |
11 ms |
5760 KB |
1_19.txt |
AC |
11 ms |
5760 KB |
1_20.txt |
AC |
13 ms |
5760 KB |
1_21.txt |
AC |
14 ms |
5760 KB |
1_22.txt |
AC |
13 ms |
5504 KB |
1_23.txt |
AC |
13 ms |
5504 KB |
1_24.txt |
AC |
13 ms |
5504 KB |
1_25.txt |
AC |
13 ms |
5504 KB |
1_26.txt |
AC |
14 ms |
5376 KB |
1_27.txt |
AC |
14 ms |
5376 KB |
1_28.txt |
AC |
9 ms |
4992 KB |
1_29.txt |
AC |
10 ms |
4992 KB |
1_30.txt |
AC |
10 ms |
5376 KB |
1_31.txt |
AC |
10 ms |
5120 KB |
1_32.txt |
AC |
12 ms |
5248 KB |
1_33.txt |
AC |
12 ms |
5248 KB |
1_34.txt |
AC |
13 ms |
5120 KB |
1_35.txt |
AC |
13 ms |
5248 KB |
1_36.txt |
AC |
13 ms |
5120 KB |
1_37.txt |
AC |
13 ms |
5248 KB |
1_38.txt |
AC |
14 ms |
5120 KB |
1_39.txt |
AC |
14 ms |
5120 KB |
1_40.txt |
AC |
14 ms |
5120 KB |
1_41.txt |
AC |
10 ms |
5120 KB |
1_42.txt |
WA |
11 ms |
4992 KB |
1_43.txt |
WA |
11 ms |
4992 KB |
1_44.txt |
WA |
11 ms |
4992 KB |
1_45.txt |
WA |
11 ms |
4992 KB |
1_46.txt |
WA |
13 ms |
4992 KB |
1_47.txt |
WA |
13 ms |
4992 KB |
1_48.txt |
AC |
13 ms |
4992 KB |
1_49.txt |
AC |
13 ms |
4992 KB |
1_50.txt |
WA |
11 ms |
4992 KB |
1_51.txt |
WA |
11 ms |
4992 KB |
1_52.txt |
AC |
11 ms |
4992 KB |
1_53.txt |
WA |
12 ms |
4992 KB |