711D - Directed Roads - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll M = 1e9 + 7;

/*
        ***        **************
        ***        **************
        ***        ***
        ***        ***
        ***        ***
        *************************
        *************************
                   ***        ***
                   ***        ***
                   ***        ***
        **************        ***
        **************        ***

*/

#define v(li) vector<ll>
#define vp(li) vector<pair<ll, ll>>
#define m(li) map<ll, ll>
#define s(li) set<ll>

#define f(i, n) for (ll i = 0; i < n; i++)
#define f1(i, n) for (ll i = 1; i < n+1; i++)
#define test(t) while (t--)
#define w(i, n) while (i < n)
#define prs(n) cout << n << " "
#define prn(n) cout << n << " "
#define newl cout << "\n"
#define pb(a) push_back(a);
#define pop pop_back()
#define in(x) insert(x)
#define fsort(v) sort(v.begin(), v.end())
#define rsort(v) sort(v.begin(), v.end(), greater<ll>())
#define rev(v) reverse(v.begin(), v.end())
#define max_ele(v) *max_element(v.begin(), v.end())
#define min_ele(v) *min_element(v.begin(), v.end())

ll binexp(ll a, ll b)
{
    if (b == 0)
        return 1;
    ll res = binexp(a, b / 2);
    if (b % 2 == 0)
        return res * res;
    else
        return a * res * res;
}

ll biexm(ll a, ll b)
{
    if (b == 0)
        return 1;
    ll res = biexm(a, b / 2);
    if (b % 2 == 0)
        return ((res % M) * (res % M)) % M;
    else
        return ((((res % M) * (res % M)) % M) * (a % M)) % M;
}

ll hcf(ll a, ll b)
{
    if (a % b == 0)
        return b;
    return hcf(b, a % b);
}
ll lcm(ll a,ll b){
    return (a*b)/(hcf(a,b));
}
vector<vector<ll>> cycles;
const ll N=2*1e5;
vector<vector<ll>> graph(N+1);
void dfs_cycle(ll u, ll p,vector<ll> &color,vector<ll> &par, ll& cyclenumber)
{
 
    if (color[u] == 2) {
        return;
    }
 
    if (color[u] == 1) {
        vector<ll> v;
        cyclenumber++;
           
        ll cur = p;
          v.push_back(cur);
 
        while (cur != u) {
            cur = par[cur];
              v.push_back(cur);
        }
          cycles.push_back(v);
        return;
    }
       par[u] = p;
 
    color[u] = 1;
 
    for (auto x : graph[u]) {
 
        if (x == par[u]) {
            continue;
        }
        dfs_cycle(x, u, color, par, cyclenumber);
    }
 
    color[u] = 2;
}
 

int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    /* Sieve */
    // ll N=1e6;
    // ll spf[N+1];
    // f(i,N+1) spf[i]=i;
    // for(ll i=2;i<N+1;i++){
    //     if(spf[i]==i){
    //         for(ll j=i*i;j<N+1;j+=i){
    //            spf[j]=i;
    //         }
    //     }
    // }


    // ll N=1e6;
    // bool isprime[N+1];
    // f1(i,N) isprime[i]=true;
    // isprime[1]=false;
    // for(ll i=2;i<N+1;i++){
    //     if(isprime[i]){
    //         for(ll j=i*i;j<N+1;j+=i) isprime[j]=false;
    //     }
    // }


    // vector<ll> primes;
    // for(ll i=2;i<N+1;i++) if(isprime[i]) primes.push_back(i);


            /* Code Starts here */
    
    ll t=1;
    // cin >> t;
    test(t)
    {   ll n;
         cin>>n;
        ll a;
        map<pair<ll,ll>,ll> mp;
        f1(i,n){
            cin>>a;
            graph[i].push_back(a);
            graph[a].push_back(i);
            ll p1=min(i,a);
            ll p2=max(i,a);
            mp[{p1,p2}]++;
        }
        for(auto x:mp){
           if(x.second==2){
              vector<ll> v1;
              v1.push_back(x.first.first);
               v1.push_back(x.first.second);
               cycles.push_back(v1);
           }
        }
        ll cyclenumber=0;
        vector<ll> color(n+1,0),par(n+1,0);
        f1(i,n){
            if(color[i]==0){
                dfs_cycle(i,0,color,par,cyclenumber);
            }
        }
        ll ans=1;
        ll ct=0;
        for(auto &x:cycles){
            ll p=x.size();
            ct+=p;
            ll temp=biexm(2,p);
            temp=(temp-2+M)%M;
            ans*=temp;
            ans%=M;
        }
        ll rem=n-ct;
        ll t1=biexm(2,rem);
        ans*=t1;
        ans%=M;
        cout<<ans<<"\n";
       
    }

    return 0;
}