SHARE
TWEET

zjtsb2

a guest Oct 24th, 2017 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #define MAXN 200010
  5. #define LL long long
  6. using namespace std;
  7.  
  8. const LL P=1000000007;
  9.  
  10. LL getPow(LL x,LL y){
  11.     LL res=1;
  12.     while(y){
  13.         if(y&1) res=res*x%P;
  14.         x=x*x%P;
  15.         y>>=1;
  16.     }
  17.     return res;
  18. }
  19.  
  20. struct edge{
  21.     int to,next;
  22.     edge(int _to=0,int _next=0):to(_to),next(_next){}
  23. }e[MAXN];
  24.  
  25. int n;
  26. int g[MAXN],nume;
  27. int p[MAXN];
  28. bool visit0[MAXN],visit[MAXN];
  29. int b[MAXN],l[MAXN],sl[MAXN],numb;
  30. int cnt[MAXN];
  31. LL f[MAXN],fac[MAXN],invfac[MAXN];
  32. LL ans=1;
  33.  
  34. void addEdge(int u,int v){
  35.     e[nume]=edge(v,g[u]);
  36.     g[u]=nume++;
  37. }
  38.  
  39. int dfs(int x){
  40.     visit[x]=1;
  41.     int numch=0;
  42.     int res=0;
  43.     for(int i=g[x];~i;i=e[i].next)
  44.         if(!visit[e[i].to]){
  45.             numch++;
  46.             res=dfs(e[i].to)+1;
  47.         }
  48.     if(numch>=2) ans=0;
  49.     return res;
  50. }
  51.  
  52. void gao(int x){
  53.     numb=0;
  54.     while(!visit[x]){
  55.         visit[x]=1;
  56.         b[++numb]=x;
  57.         x=p[x];
  58.     }
  59.     int pos=0;
  60.     for(int i=1;i<=numb;i++){
  61.         l[i]=dfs(b[i]);
  62.         if(l[i]) pos=i;
  63.     }
  64.     if(!pos){
  65.         cnt[numb]++;
  66.         return;
  67.     }
  68.     for(int i=1;i<=numb;i++){
  69.         b[i+numb]=b[i];
  70.         l[i+numb]=l[i];
  71.         b[i]=b[i+pos-1];
  72.         l[i]=l[i+pos-1];
  73.     }
  74.     for(int i=1;i<=numb;i++) sl[i]=sl[i-1]+l[i];
  75.     LL res1=0,res2=0;
  76.     if(sl[numb]-sl[numb-(l[1]-1)]==0){
  77.         res1=1;
  78.         for(int i=2;i<=numb;i++){
  79.             if(!l[i]) continue;
  80.             LL temp=0;
  81.             if(sl[i-1]-sl[max(0,i-l[i])]==0) temp++;
  82.             if(sl[i-1]-sl[max(0,i-l[i]-1)]==0) temp++;
  83.             res1=res1*temp%P;
  84.         }
  85.     }
  86.     if(sl[numb]-sl[numb-l[1]]==0){
  87.         res2=1;
  88.         for(int i=2;i<=numb;i++){
  89.             if(!l[i]) continue;
  90.             LL temp=0;
  91.             if(sl[i-1]-sl[max(0,i-l[i])]==0) temp++;
  92.             if(sl[i-1]-sl[max(0,i-l[i]-1)]==0) temp++;
  93.             res2=res2*temp%P;
  94.         }
  95.     }
  96.     ans=ans*(res1+res2)%P;
  97. }
  98.  
  99. void init(){
  100.     f[0]=1;
  101.     for(int i=2;i<=n;i++) f[i]=f[i-2]*(i-1)%P;
  102.     fac[0]=1;
  103.     for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%P;
  104.     invfac[n]=getPow(fac[n],P-2);
  105.     for(int i=n-1;i>=0;i--) invfac[i]=invfac[i+1]*(i+1)%P;
  106. }
  107.  
  108. LL getC(int x,int y){
  109.     return fac[x]*invfac[y]%P*invfac[x-y]%P;
  110. }
  111.  
  112. int main(){
  113. #ifdef DEBUG
  114.     freopen("E.in","r",stdin);
  115. #endif
  116.     memset(g,-1,sizeof g);
  117.     scanf("%d",&n);
  118.     for(int i=1;i<=n;i++){
  119.         scanf("%d",p+i);
  120.         addEdge(p[i],i);
  121.     }
  122.     for(int i=1;i<=n;i++)
  123.         if(!visit[i]){
  124.             int x=i;
  125.             for(;!visit0[x];x=p[x]) visit0[x]=1;
  126.             gao(x);
  127.         }
  128.     init();
  129.     for(int i=1;i<=n;i++)
  130.         if(cnt[i]){
  131.             LL res=0;
  132.             for(int j=0;j<=cnt[i];j+=2)
  133.                 if(i>=3 && (i&1)) res=(res+getC(cnt[i],j)*f[j]%P*getPow(i,j/2)%P*getPow(2,cnt[i]-j))%P;
  134.                 else res=(res+getC(cnt[i],j)*f[j]%P*getPow(i,j/2))%P;
  135.             ans=ans*res%P%P;
  136.         }
  137.     printf("%lld\n",ans);
  138.     return 0;
  139. }
RAW Paste Data
Top