Counting of Trees [NIKKEI Programming Contest 2019-2 B]

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_b

解説

https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8371235

300点問題ではあるが、累乗を使う所があるので、そのライブラリを持っていないと厳しい。
mod上での掛け算は理解しているとして進める（かけてmodとるだけだけど）。
後、色々コーナーケースがあるので注意。

根から順番に組み合わせを確定させていくことを考える。
頂点1は根なのでD[0]=1である必要があり、かつ、ここだけである必要がある。
cnt[d] := D[i]=dである頂点の個数
以上のように置くと、cnt[0]=1である必要がある。

距離が1の頂点について考えると、これは全て根につなげるしか無い。
よって、1通り。

距離が2の頂点について考える。
その中の1つの頂点について考えると、これを距離が1の頂点のどれかにつなげると考えるとcnt[1]通りある。
他の頂点についても同様であるため、距離が2の頂点を距離が1の頂点につなげる組み合わせは、
cnt[1]^cnt[2]通りとなる。
この計算は、以下も同様となるので、求めたい答えはcnt[i]^cnt[i+1]の総積である。

あと、距離は0から順番に存在する必要がある。
距離3と5の頂点はあるけど、距離4の頂点は無いというのはありえない。

int N, D[101010];
//---------------------------------------------------------------------------------------------------
mint solve() {
    map<int, int> cnt;
    rep(i, 0, N) cnt[D[i]]++;

    int n = cnt.size();
    rep(i, 0, n) if (cnt[i] == 0) return 0;
    if (cnt[0] != 1) return 0;
    if (D[0] != 0) return 0;

    mint res = 1;
    rep(i, 1, n) res *= mint(cnt[i - 1]) ^ cnt[i];
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> D[i];
    cout << solve() << endl;
}