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
AC × 4
WA × 1
AC × 46
WA × 13
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