読者です 読者をやめる 読者になる 読者になる

Codeforces Round #369 (Div. 2) D. Directed Roads

Codeforces 競プロ

問題

codeforces.com

考察

提示されているグラフは、各ノードが親を1つだけ持つ森になります。
「親が1つだけ」なので、森のそれぞれの木は必ずループを1つ持ちます。

not confusingな木を作るためには、ループを構成するどれかの辺を逆にすれば良いです。
いくつ逆にしても良いですが、「1つも逆にしない」「全て逆にする」とまたループになってしまうのでダメです。
ループを構成する辺の数をXとおくと、 2^{T} - 2のパターンがあります。

また、ループでない辺は反転してもしなくても良いので、木全体の辺の数をYとすると以下のパターン数になります。
 2^{Y-T} * ( 2^{T} - 2 )

これを各木に対して行うのですが、全ての木のパターン数を掛けあわせるので、指数部分は足し合わされて簡単になります。
全てのループでない辺の数をA、各木のループしている辺の数を T_{i}と置くと、答えは↓の式で表されます。

 2^{A} * {\prod_i 2^{T_{i}} - 2 }

よって、各木のループしている辺の数さえ分かれば答えが算出できます。

実装上の工夫

ループしている辺の数は、多少特殊なDFSをすると簡単に求まります。

  1. ノードの状態を4つに分ける (初期状態・訪れた・ループ中・通り過ぎた)
  2. ループをカウントする専用のDFSを分ける

これにより、上手くループをカウントすることができます。
詳細はコードを見てください。

コード

const int MAX_N = (ll)(1e5) * 2 + 100;
int used[MAX_N];
vi par;
enum V_ST {
        INIT = 0,
        GO,
        AWAY,
        LOOP
};
vi loop;

void dfs2(int v) {
    loop[loop.size()-1]++;

    used[v] = LOOP;
    if(used[par[v]] == LOOP)
        return;
    dfs2(par[v]);
}

void dfs(int v) {
    used[v] = GO;
    if(used[par[v]] == INIT) {
        dfs(par[v]);
    }
    else if(used[par[v]] == AWAY) {
        used[v] = AWAY;
        return;
    }
    else {
        loop.push_back(0);
        dfs2(par[v]);
    }
    used[v] = AWAY;
}

int main() {
    int n;
    cin >> n;
    vi in(n, 0);
    rep(i, n) {
        int t;
        cin >> t;
        t--;
        par.push_back(t);
    }

    rep(i, n) {
        if(used[i] == INIT) {
            dfs(i);
        }
    }

    ll rem = n - accumulate(all(loop), 0ll);
    ll ans = fpow(2, rem, MOD);
    tr(it, loop) {
        ans *= (fpow(2, *it, MOD) - 2);
        ans %= MOD;
    }

    cout << ans << endl;
    
    return 0;
}