問題一覧 > 通常問題

No.1302 Random Tree Score

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 72
作問者 : nok0nok0 / テスター : tpynerivertpyneriver Kite_kumaKite_kuma
10 ProblemId : 5389 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-11-09 12:02:40

問題文

頂点に $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$

  • $N$ は整数である。
  • $2 \le N\le 10^5$

    • 出力

    スコアの平均値を $\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もしくは右上の雲マークをクリックしてアカウントを作成してください。