問題一覧 > 通常問題

No.1302 Random Tree Score

レベル : / AI推定難易度 : 2275 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 81
作問者 : nok0 / テスター : tpyneriver Kite_kuma
お気に入りにしたユーザー ProblemId : 5389 / 自分の提出
問題文最終更新日: 2020-11-09 12:02:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 276 (順位表) の他の問題:

Problem Statement

For a tree with $N$ vertices numbered from $1$ to $N$, define the score of the tree as

score $:=\displaystyle \prod_{i=1}^N$ (degree of vertex $i$)

.

There are $N ^ {N - 2}$ trees with $N$ vertices numbered from $1$ to $N$. Find the average of the score over these trees and print it $\mbox{mod } 998244353$.

More precisely, under the constraints of this problem, it can be proved that the average is a rational number, that is, it can be expressed as an irreducible fraction $\frac{P}{Q}$, and that an integer $R$ satisfying $R×Q≡P(\mbox{mod } 998244353),\ 0 \le R< 998244353$ is uniquely determined. Print this $R$.

Input

$N$

  • $N$ is an integer.
  • $2 \le N\le 10^5$

    • Output

    Print the average of the score $\mbox{mod } 998244353$.

    Sample

    Sample 1
    Input
    3
    Output
    2

    There are $3$ trees with $3$ vertices. In every tree, the vertex degrees are {$2, 1, 1$}, so the score is $2 × 1 × 1 = 2$. Therefore, the average is also $2$.

    Sample 2
    Input
    4
    Output
    249561092

    There are $16$ trees with $4$ vertices. Among them, $12$ trees have the $4$ vertex degrees {$2, 2, 1, 1$}, and the remaining $4$ trees have {$3, 1, 1, 1$}, so the average of the score is $\frac{4 × 12 + 3 × 4}{16} = \frac{15}{4}$. Since $249561092×4≡15(\mbox{mod } 998244353) $, print $249561092$.

    Sample 3
    Input
    27182
    Output
    877912165

    Print the answer $\mbox{mod } 998244353$.

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