ARC 114

Table of Contents

B - Special Subsets

条件より $i$ から $f(i)$ に辺を張ったグラフを作り、このうちサイクルを成しているサブグラフの頂点集合が $T$ になる。 各サブグラフは独立しているからサイクルを成しているサブグラフの個数を $n$ とすると $2^n - 1$ が答え。

void solve() {
    ll N;
    cin >> N;
    vll f(N);
    rep(i, N) {
        cin >> f[i];
        f[i]--;
    }

    scc_graph graph(N);
    rep(i, N) {
        graph.add_edge(i, f[i]);
    }

    vvint scc = graph.scc();
    ll cnt = 0;
    for (auto& x : scc) {
        if (x.size() > 1) {
            cnt++;
        } else {
            // 大きさ1のときは自己ループしていればカウント
            if (x[0] == f[x[0]])
                cnt++;
        }
    }

    mint ans = ((mint)2).pow(cnt) - 1;
    cout << ans.val() << endl;
}