問題一覧 > 通常問題

No.3451 Same Numbers

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 : 👑 potato167 / テスター : noya2
ProblemId : 13071 / yukicoder contest 493 (順位表) / 自分の提出
問題文最終更新日: 2026-02-21 03:15:37
yukicoder contest 493の他の問題:

問題文

正整数 $N, M, E$ が与えられます。

$k = 1, 2, \dots , N$ について、以下の問いに答えてください。

$1$ から $N$ までの番号のついた $N$ 個のボールがあります。

これら $N$ 個のボールのみが入った箱があります。

$M$ 回の操作を行います。$i$ 回目の操作では以下の行動をします。

  • 箱の中のボールを一様ランダムに $1$ つ選び取り出し、箱の外に置く。その後 $k \leq i$ ならば、$(i + 1 - k)$ 回目に取り出したボールを箱の中に戻す。

以下の条件を満たす整数 $t(1\leq t\leq M)$ の個数をスコアとしたとき、スコアの $E$ 乗の期待値を$\pmod{998244353}$ で求めてください。

  • $t$ 回目の操作で取り出したボールに書かれた番号は、$1$ 回目の操作で取り出したボールに書かれた番号と同じ。
期待値$\pmod{998244353}$ とは 求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 $\frac{P}{Q}$ で表した時、$Q \not \equiv 0 \pmod{998244353}$ となることも証明できます。 よって、$R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353$ を満たす整数 $R$ が一意に定まります。 この $R$ を答えてください。

制約

  • $1\leq N\leq 10^{5}$
  • $1\leq M\leq 10^{5}$
  • $1\leq E\leq 10^{5}$
  • 入力は全て整数

入力

$N$ $M$ $E$

出力

$N$ 行出力してください。

$i$ 行目には $k = i$ であるときの答えを出力してください。

サンプル

サンプル1
入力
3 3 2
出力
887328317
499122179
1
サンプル2
入力
1 2 100000
出力
538261388
サンプル3
入力
9 24 167
出力
266696013
354954351
889968913
422652273
484325722
488941374
396408879
596917142
76920761

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