Directed Roads [Codeforces 369 : Div2 D]

問題

http://codeforces.com/contest/711/problem/D

n頂点の有向グラフがある。
全ての頂点から1本ずつ有向辺が出ている。
有向辺をひっくり返す組合せは2^n通りあるが、このうち、ループが無い組合せは何通り？
10^9+7を法として答えよ。

2 <= n <= 2*10^5

考察

1. なんかTopCoderみたいな問題だな
2. こういう系はまずは例を使って実験してみる
3. 有向グラフだが、自由に方向を変えるので別に無向グラフと変わりない

4. ループになっている頂点とループにくっついている頂点とに分けて考えることができそう

5. ループにくっついている頂点からの辺は特に方向がループに関係しない
6. なので、この辺を消して、カウントしておく -> del()

7. ループとなっている頂点はUnion-Findで各成分の頂点数を数えておく
8. ループとなっているある成分の頂点数がmの時、辺の数もm
9. ループが完成してしまうのは、2^m通りのうち2通りで、それ以外はループにならない
10. なので、ループができないのは、各成分(2^m - 2)通り

11. あとはdel()でカウントしておいた関係ない個数delnumを使った「2^delnum通り」と各成分「(2^m - 2)の総乗」との積を10^9+7を法として計算して答え

実装

http://codeforces.com/contest/711/submission/20243781

typedef long long ll;
ll MOD = 1000000007;
ll modpow(ll a, ll n) {
	a %= MOD;
	if (a == 0) return 0;
	ll r = 1;
	while (n) r = r*((n % 2) ? a : 1) % MOD, a = a*a%MOD, n >>= 1;
	return r;
}
template<int um> class UF { // from kmjp
public:
	vector<int> par;
	UF() { par = vector<int>(um, 0); rep(i, 0, um) par[i] = i; }
	int operator[](int x) { return par[x] == x ? x : par[x] = operator[](par[x]); }
	void operator()(int x, int y)
	{
		x = operator[](x); y = operator[](y);
		if (x != y) par[x] = y;
	}
};
//-----------------------------------------------------------------
int N;
vector<int> E[201010];
//-----------------------------------------------------------------
int delnum = 0;
void del() {
	queue<int> que;

	rep(i, 0, N) if (E[i].size() == 1) que.push(i);
	while (!que.empty()) {
		int i = que.front(); que.pop();

		int j = E[i][0];
		E[i].erase(find(E[i].begin(), E[i].end(), j));
		E[j].erase(find(E[j].begin(), E[j].end(), i));
		delnum++;

		if (E[j].size() == 1) que.push(j);
	}
}
//-----------------------------------------------------------------
int cnt[201010];
int main() {
	cin >> N;
	rep(i, 0, N) {
		int a;
		scanf("%d", &a);
		a--;
		E[i].push_back(a);
		E[a].push_back(i);
	}

	del();

	UF<201010> uf;
	rep(i, 0, N) cnt[i] = 1;
	rep(i, 0, N) for (int j : E[i]) {
		if (uf[i] != uf[j]) {
			int c = cnt[uf[i]] + cnt[uf[j]];
			uf(i, j);
			cnt[uf[i]] = c;
		}
	}

	ll ans = 0;
	ans = modpow(2, delnum);
	rep(i, 0, N) if (uf[i] == i && 0 < E[i].size()) ans = (ans * (modpow(2, cnt[i]) - 2)) % MOD;
	cout << ans << endl;
}