| 12345 |
- #include <iostream>
- #include <queue>
- #include <vector>
- using namespace std;constexpr long long MOD=1000000007;long long pw(long long a,int b){long long r=1;for(;b;b>>=1,a=a*a%MOD)if(b&1)r=r*a%MOD;return r;}
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;vector<int>to(n),in(n);for(int&i:to){cin>>i;--i;++in[i];}queue<int>q;vector<bool>removed(n),seen(n);for(int i=0;i<n;++i)if(in[i]==0)q.push(i);int peeled=0;while(!q.empty()){int u=q.front();q.pop();removed[u]=true;++peeled;if(--in[to[u]]==0)q.push(to[u]);}long long ans=pw(2,peeled);for(int s=0;s<n;++s)if(!removed[s]&&!seen[s]){int len=0,u=s;do{seen[u]=true;++len;u=to[u];}while(u!=s);ans=ans*((pw(2,len)-2+MOD)%MOD)%MOD;}cout<<ans<<'\n';}
|
