Codeforces 711D(DFS找有向环+组合数)

Codeforces 711D
题意：给一个图，$n$个点$n$条边，可以让任意几条边方向取反，问有多少种方案使得图中没有环。
对于一个环，要使得它环被破坏，那么必须取反环上的一些边，不能不反或者全反，否则新的环将出现。因为图中给出$i->a_i$边的图每个点出度至多为1，所以没有大环包含小环的情况，也没有取反一条边后形成新环的可能，因为路径$u->v$如果取反一条边后形成新环，则$u->v$一定存在，与出度至多为1矛盾。所以每个环对答案的贡献为$2^{k_i}-2$, $k_i$为环$i$的大小。不在任何环上的点指出的边可以任意取反或不取反，对环的构成无影响。根据乘法原理，得到最终答案为$2^{n-\sum_{i=1}^{siz}k_i}\prod_{i=1}^{siz}(2^{k_i}-2)$，$siz$为环的总个数
知识点：1、DFS 开一个 cnt 数组辅助求解有向环
2、图中给出$i->a_i$边的图每个点出度至多为1，所以没有大环包含小环的情况。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

const LL MAXN = 200000 + 5, MO = 1e9 + 7;

LL n, a[MAXN], vis[MAXN], cnt[MAXN], ans, siz, k[MAXN];

LL poww(LL a, LL b) {
    LL bs = a, ret = 1;
    while (b) {
        if (b & 1) ret = (ret * bs) % MO;
        bs = (bs * bs) % MO, b >>= 1;
    }
    return ret;
}

void dfs(LL u, LL src, LL d) {
    cnt[u] = d, vis[u] = src;
    if (!vis[a[u]]) dfs(a[u], src, d + 1); else if (vis[a[u]] == src) {
        k[++siz] = cnt[u] - cnt[a[u]] + 1;
        ans = (ans * (poww(2ll, k[siz]) - 2ll)) % MO;
    }
}

void clean() {
    siz = 0, ans = 1, ms(vis, 0);
}
int solve() {
    clean();
    for (LL i = 1; i <= n; i++) scanf("%lld", &a[i]);

    for (LL i = 1; i <= n; i++) if (!vis[i]) dfs(i, i, 0ll);

    LL sum = 0ll;
    for (LL i = 1; i <= siz; i++) sum += k[i];
    ans = (ans * poww(2ll, n - sum)) % MO;

    printf("%lld\n", ans);
    return 0; 
}
int main() {
    scanf("%lld", &n), solve();
    return 0;
}