問題一覧 > 通常問題

No.1302 Random Tree Score

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

問題文

頂点に 1 から N の番号がついた N 頂点の木について、その木のスコアを

スコア :=∏i=1N (頂点 i の次数)

と定義します。

頂点に 1 から N の番号がついた N 頂点の木は NN−2 個存在しますが、それらについてスコアの平均値を求め、mod 998244353 で出力してください。

より正確には、平均値が有理数、つまりある既約分数 PQ で表せること、更に R×Q≡P(mod 998244353), 0≤R<998244353 を満たす整数 R が一意に定まることがこの問題の制約より証明できます。よって、この R を出力してください。

入力

N

  • N は整数である。
  • 2≤N≤105

    • 出力

    スコアの平均値を 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} なのでスコアの平均値は 4×12+3×416=154 です。 249561092×4≡15(mod 998244353) なので、 249561092 を出力してください。

    サンプル3
    入力
    27182
    出力
    877912165

    mod 998244353 で出力してください。

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。