問題
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; }