No.1302 Random Tree Score
タグ : / 解いたユーザー数 71
作問者 : nok0 / テスター : tpyneriver Kite_kuma
問題文
頂点に $1$ から $N$ の番号がついた $N$ 頂点の木について、その木のスコアを
スコア $:=\displaystyle \prod_{i=1}^N$ (頂点 $i$ の次数)
と定義します。
頂点に $1$ から $N$ の番号がついた $N$ 頂点の木は $N ^ {N - 2}$ 個存在しますが、それらについてスコアの平均値を求め、$\mbox{mod } 998244353$ で出力してください。
より正確には、平均値が有理数、つまりある既約分数 $\frac{P}{Q}$ で表せること、更に $R×Q≡P(\mbox{mod } 998244353),\ 0 \le R< 998244353$ を満たす整数 $R$ が一意に定まることがこの問題の制約より証明できます。よって、この $R$ を出力してください。
入力
$N$
出力
スコアの平均値を $\mbox{mod } 998244353$ で出力してください。
サンプル
サンプル1
入力
3
出力
2
$3$ 頂点の木は $3$ 個存在しますが、どの木でも頂点の次数が {$2, 1, 1$} であるため スコアは $2 × 1 × 1 = 2$ です。よって平均値も $2$ です。
サンプル2
入力
4
出力
249561092
$4$ 頂点の木は $16$ 個存在します。そのうち $12$ 個は $4$ 頂点の次数が {$2, 2, 1, 1$} 、残りの $4$ 個は {$3, 1, 1, 1$} なのでスコアの平均値は $\frac{4 × 12 + 3 × 4}{16} = \frac{15}{4}$ です。 $249561092×4≡15(\mbox{mod } 998244353) $ なので、 $249561092$ を出力してください。
サンプル3
入力
27182
出力
877912165
$\mbox{mod } 998244353$ で出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。