[Codeforces] 711D. Directed Roads

題目連結:http://codeforces.com/problemset/problem/711/D

---

小品(?的圖論題。首先有個小觀察，這種給法的圖，在每一個連通塊(?中，只會有一個環，不過還是可能會有很多連通塊就是了。所以先考慮一個連通塊的情況，發現若他的環有$k$個邊，且整個連通塊有$n$個邊的話，他的方法數就會是$(2^k-2)\cdot(2^{n-k})$，想法大致就是，環上每個邊都可以選擇要換或不換扣掉全換跟全部換，再乘以其他大家的可能性就好了。至於多個連通塊的情況就直接把他們乘在一起就好了，畢竟他們是獨立的。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define PB push_back
#define FF first
#define SS second
const int N = 200000 + 5;
const lld MOD_BASE = 1e9 + 7;

class DJS{
	private:
		vector<int> arr, sz;
	public:
		void init(int n){
			arr.resize(n);
			sz.resize(n);
			for(int i=0;i<n;i++){
				arr[i]=i;
				sz[i]=1;
			}
		}
		int size(int x){return sz[query(x)];}
		int query(int x){
			if(arr[x]!=x) arr[x] = query(arr[x]);
			return arr[x];
		}
		void merge(int a, int b){
			if(size(a) < size(b)) swap(a, b);
			int aa = query(a), bb = query(b);
			if(aa==bb) return;
			arr[aa]=bb;
			sz[bb]+=sz[aa];
		}
} djs;

vector<int> G[N];
int dfn[N];
bool done[N];
int dfs(int);
lld qPow(lld,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	djs.init(n+1);
	for(int i=1;i<=n;i++){
		int x; cin>>x;
		G[i].PB(x);
		djs.merge(x, i);
	}
	vector<lld> ans;
	for(int i=1;i<=n;i++){
		if(done[djs.query(i)]) continue;
		dfn[i]=1;
		int huan = dfs(i);
		if(huan==0) continue;
		ans.PB((((qPow(2, huan)-2+MOD_BASE)%MOD_BASE) * qPow(2, djs.size(i)-huan))%MOD_BASE);
		dfn[i]=0;
		done[djs.query(i)] = 1;
	}
	lld res = !ans.empty();
	for(auto i: ans) res = (res*i)%MOD_BASE;
	cout<<res<<'\n';
	return 0;
}

int dfs(int x){
	for(auto i: G[x]){
		if(dfn[i] != 0) return dfn[x]+1-dfn[i];
		dfn[i] = dfn[x]+1;
		int ret = dfs(i);
		dfn[i]=0;
		if(ret!=0) return ret;
	}
	return 0;
}

lld qPow(lld a, int x){
	lld ret = 1;
	while(x){
		if(x&1) ret = (ret*a)%MOD_BASE;
		x>>=1;
		a = (a*a)%MOD_BASE;
	}
	return ret;
}