No.1302 Random Tree Score - yukicoder

問題

$N$ 頂点ラベル付き木で、頂点 $v$ の次数が $d_v$ であるような木のスコアを $\prod_{v} d_v$ と定める。

$N$ 頂点ラベル付き木は全部で $N^{N-2}$ 個あるが、それらのスコアの平均値 $\pmod{998,244,353}$ を求めよ

制約

• $2 \leq N \leq 10^5$

考察

まず頂点 $v$ の次数が $d_v$ であるような $N$ 頂点ラベル付き木の個数は、以下で表される。

$$ (N-2)! \prod_v \frac{1}{(d_v - 1)!} $$

これは「Prüfer コード」を使うと求められる (参考記事)。 ということで、スコアの平均は以下の式で求まる。

$$ \frac{(N-2)!}{N^{N-2}} \sum_{(d_v): \sum_v d_v = 2(N-1)} \prod_v \frac{d_v}{(d_v - 1)!} $$

$\frac{(N-2)!}{N^{N-2}}$ は最後に掛けることにして、以降は以下の値をどう計算するか考える。

$$ \sum_{(d_v): \sum_v d_v = 2(N-1)} \prod_v \frac{d_v}{(d_v - 1)!} $$

まずこの値は、 $f(x) = \sum_{k=1}^{\infty} \frac{k}{(k - 1)!}x^k$ という形式的冪級数によって $[x^{2(N-1)}]f^N(x)$ と表せる。 さらにこの $f(x)$ は、 $F(x) = xe^x = \sum_{k=1}^{\infty} \frac{x^k}{(k-1)!}$ によって $f(x) = xF’(x) = x(1 + x)e^x$ と表せる。

よって $[x^{2(N-1)}]f^N(x) = [x^{2(N-1)}] x^N (1+x)^N e^{Nx} = [x^{N-2}] (1+x)^N e^{Nx}$ と変形できる。後は

$$ \begin{align} (1+x)^N &= \sum_{k=0}^{N} \binom{N}{k} x^k \\ e^{Nx} &= \sum_{k=0}^{\infty} \frac{N^k}{k!} x^k \end{align} $$

を使えば値が求まる。

実装例

#586123 (C++17) No.1302 Random Tree Score - yukicoder

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <atcoder/modint>
#include <iostream>
#include <vector>

template <class T>
struct Combination { ... };

using namespace std;

using mint = atcoder::modint998244353;
const Combination<mint> C(200000);

void solve() {
    int n;
    cin >> n;

    mint ans = 0;
    for (int k = 0; k <= n - 2; ++k) {
        ans += C.binom(n, k) * mint(n).pow(n - 2 - k) * C.invfact(n - 2 - k);
    }
    cout << (ans * C.fact(n - 2) / mint(n).pow(n - 2)).val() << "\n";
}