New Year Contest 2015 E - ひも

問題: E - ひも

問題概要

$N ( \leq 10^5)$ 個の区別できるノードがある。 $i (1 \leq i \leq N)$ 番目のノードの次数が $a_i (1 \leq a_i \leq 3) $であり、すべてのノードが直接または間接的に辺で繋がれており、かつ辺が全体で $N-1$ 本となるようなグラフの数を $10^9+7$ で割った余りを求めよ。

解法概要

$N$ 個のノード、$N-1$ 本の辺、それらがすべて繋がっている、ということは問題の条件通りに作ったグラフは木になる。また、辺は $N-1$ 本だから、ノードの次数の合計は $2 (N-1) $ となる。

したがって、 $\sum_{i=1}^N a_i \neq 2 (N-1)$ の場合答えは 0 である。

以下は $\sum_{i=1}^N a_i = 2 (N-1)$ の場合のみを考える。

上図は Sample Input 1 を図にしたものである。

木を作る操作の言い換え

これをもとに考えると、木を作る操作は次のように言い換えられる。

1. 「残りの腕が 1 本のパーツ」と「残りの腕が 2,3 本のパーツ」を1つずつ選んで繋ぐ。
2. 1 の操作を $N-2$ 回繰り返す。
3. 「残りの腕が 2, 3 本のノード」がなくなるので、最後に「残りの腕が 1 本のパーツ」同士を繋ぐ。

1 について、残りのパーツ数の合計が 3 以上のうちは次のように「残りの腕が 1 本のパーツ」同士を繋げることはできない。これらを繋げてしまうと、今後勝手に腕を増やさない限り $N$ 個のノードからなる木を作ることができなくなってしまう。

元々「残りの腕が 2,3 本のパーツ」だったものが、「残りの腕が 1 本のパーツ」と繋げることで残りの腕が 1 本になったら、「残りの腕が 1 本のパーツ」に移動する。

元々の腕が3本あっても、「残りの腕が 1 本のパーツ」と繋ぐ対象に2回選ばれることで「残りの腕が 1 本のパーツ」になれる。

最後 ($N-1$ 回目の操作) は「残りの腕が1本のパーツ」だけになるので、この2つを繋ぐことになる。 (もし $N-1$ 回目まで残りの腕が2本以上あるパーツが残っているとすると、多重辺や自己ループを作らない限り各ノードの次数の制約を満たすことはできない。しかし多重辺や自己ループを入れようとすると、今度は辺の数が $N-1$ を超えてしまう)

重複を作らないようにする

しかし前の節での木の作り方をそのまま式にして数えようと思ったときに、同じ木を2回以上数えてしまう可能性がある。例えば、

• ノード 1 とノード 3 を繋ぐ
• ノード 4 とノード 5 を繋ぐ

これらの操作はどちらを先に実行しても結果は同じである。

そこで、操作の対象となるパーツのうち「残りの腕が 1 本のパーツ」の選び方を「その時点で最もノード番号の小さいもの (複数ノードからなるパーツの場合は残っている腕を持つノードの番号が最も小さいもの) 」と固定する。操作の順番が自由だと都合が悪いときに、順番を固定しても一般性が失われないものについて「条件を満たすものの中から最も添字の小さいもの」から操作するようにすると考えやすくなる問題は競プロでよくある。

すると、「残りの腕が 2,3 本のパーツ」の選び方の順番は $(N-2)!$ 通りになる。 ($N-1$ 回目の操作以外は「残りの腕が 1 本のパーツ」同士をくっつけることはできないので $N-2$)

しかし、「残りの腕が 1 本のパーツ」の選び方を固定してもまだ重複の可能性がある。

腕が3本あるパーツがある場合、出来上がる木の根を適当に (例えばノード 1 に) 固定したとしても、左の子と右の子を入れ替えたような木をどちらもカウントしてしまう。 今回作る木は頂点こそ区別するが、辺を区別しないので、それらは 1 つとしてカウントしなければならない。 そのため、腕が3本あるパーツの数を $t$ として $2^t$ で割っておく必要がある。

したがって、今回求めるべきグラフの数は

$$\frac{(N-2)!}{2^t}$$

である。ただし $t$ は $a_i = 3$ となる $i$ の数である。

ソースコード

#include <iostream>

using namespace std;

using ll =  long long;

constexpr ll MOD = 1[f:id:noimin:20201209221656p:plain]000000007;
constexpr int N_MAX = 100000;

ll fact[N_MAX+1], rfact[N_MAX+1];

ll modpow(ll a, ll p) {
    ll ret = 1LL;
    while(p) {
        if(p & 1) {
            ret = (ret * a) % MOD;
        }
        a = (a * a) % MOD;
        p >>= 1;
    }
    return ret;
}

void init_fact(ll n) {
    fact[0] = fact[1] = 1;
    rfact[0] = rfact[1] = 1;
    for(ll i=2;i<=n;++i) {
        fact[i] = (fact[i-1] * i) % MOD;
        rfact[i] = modpow(fact[i], MOD-2);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    init_fact(n);
    ll a[n], s = 0;
    for(int i=0;i<n;++i) {
        cin >> a[i];
        s += a[i];
    }
    if(s != 2 * (n-1)) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = fact[n-2];
    for(int i=0;i<n;++i) {
        ans *= rfact[a[i]-1];
        ans %= MOD;
    }

    cout << ans << endl;
}

所感

この答えの式はPrüfer sequence として有名らしい。 (参考: New Year Contest 2015 E問題 - ひも - ゲームにっき（仮）別館（仮）)