fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; ++i)
  3. #define fi first
  4. #define se second
  5. #define el "\n"
  6. #define pb push_back
  7. #define sz(a) (int)a.size()
  8. #define FILL(a,x) memset(a,x,sizeof(a))
  9.  
  10. using namespace std;
  11. typedef long long ll;
  12. typedef pair<int,int> ii;
  13.  
  14. const int N = 100000 + 5;
  15. const int MOD = 1000000007;
  16.  
  17. int n;
  18. int p[N], indeg[N];
  19. vector<int> revG[N];
  20. int incy[N], dep[N], vis[N];
  21.  
  22. int spf[N];
  23. int pw[N];
  24.  
  25. void sieve(int m){
  26.     FILL(spf,0);
  27.     FOR(i,2,m) if(!spf[i]){
  28.         for(int j=i;j<=m;j+=i) if(!spf[j]) spf[j]=i;
  29.     }
  30. }
  31.  
  32. ll power_mod(ll a,int e){
  33.     ll r = 1;
  34.     while(e){
  35.         if(e & 1) r = r * a % MOD;
  36.         a = a * a % MOD;
  37.         e >>= 1;
  38.     }
  39.     return r;
  40. }
  41.  
  42. int main(){
  43.     ios::sync_with_stdio(false);
  44.     cin.tie(NULL); cout.tie(NULL);
  45.  
  46.     cin >> n;
  47.     FOR(i,1,n){
  48.         cin >> p[i];
  49.         indeg[p[i]]++;
  50.         revG[p[i]].pb(i);
  51.     }
  52.  
  53.     FILL(incy,1);
  54.     queue<int> q;
  55.     FOR(i,1,n) if(indeg[i]==0) q.push(i);
  56.     while(!q.empty()){
  57.         int u = q.front(); q.pop();
  58.         incy[u] = 0;
  59.         int v = p[u];
  60.         indeg[v]--;
  61.         if(indeg[v]==0) q.push(v);
  62.     }
  63.  
  64.     queue<int> q2;
  65.     FILL(vis,0);
  66.     FOR(i,1,n) if(incy[i]){
  67.         vis[i]=1;
  68.         dep[i]=0;
  69.         q2.push(i);
  70.     }
  71.     int H = 0;
  72.     while(!q2.empty()){
  73.         int u = q2.front(); q2.pop();
  74.         if(dep[u]>H) H = dep[u];
  75.         for(int j=0;j<sz(revG[u]);++j){
  76.             int v = revG[u][j];
  77.             if(!vis[v]){
  78.                 vis[v]=1;
  79.                 dep[v]=dep[u]+1;
  80.                 if(dep[v]>H) H = dep[v];
  81.                 q2.push(v);
  82.             }
  83.         }
  84.     }
  85.  
  86.     sieve(n);
  87.     FILL(pw,0);
  88.     FILL(vis,0);
  89.     FOR(i,1,n) if(incy[i] && !vis[i]){
  90.         int u = i, len = 0;
  91.         while(!vis[u]){
  92.             vis[u]=1;
  93.             len++;
  94.             u = p[u];
  95.         }
  96.         int x = len;
  97.         while(x>1){
  98.             int pr = spf[x];
  99.             int cnt = 0;
  100.             while(x%pr==0){
  101.                 x/=pr;
  102.                 cnt++;
  103.             }
  104.             if(cnt > pw[pr]) pw[pr] = cnt;
  105.         }
  106.     }
  107.  
  108.     ll L = 1;
  109.     FOR(i,2,n) if(pw[i]){
  110.         L = L * power_mod(i, pw[i]) % MOD;
  111.     }
  112.  
  113.     ll ans = (L + (ll)H) % MOD;
  114.     cout << ans << el;
  115.     return 0;
  116. }
  117.  
  118.  
Success #stdin #stdout 0.01s 7876KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/NpDhWq
language:
C++14 (clang 8.0)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!