問題一覧 > 通常問題

No.3770 Sum of Pow of Distinct Count

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 4
作問者 : apricity / テスター : kaichou243 marc2825
お気に入りにしたユーザー ProblemId : 13647 / 自分の提出
問題文最終更新日: 2026-10-15 04:58:20
yukicoder contest 518 (順位表) の他の問題:

問題文

正整数 $N,M,K$ が与えられます．

整数列 $A$ に対して， $f(A)$ を $A$ に現れる値の種類数とします．

$1$ 以上 $M$ 以下の整数からなる長さ $N$ の整数列 $A$ は $M^N$ 通り考えられますが，それらすべてに対する $f(A)^k$ の総和を $S_k$ とおきます．

$k = 1,2,\dots,K$ に対して， $S_k$ を $998244353$ で割った余りを求めてください．

入力

$N\ M\ K$
  • 入力は全て整数．
  • $1 \leq N \leq 10^{18}$
  • $1 \leq M \leq 10^{18}$
  • $1 \leq K \leq 2\times 10^5$

出力

$K$ 行出力してください． $k$ 行目には $S_k$ を $998244353$ で割った余りを出力してください．

サンプル

サンプル1
入力
3 2 4
出力
14
26
50
98

$A$ として考えられるものは $2^3 = 8$ 通りあります．そのうち， $(1,1,1)$ と $(2,2,2)$ の $2$ 通りについて $f(A) = 1$ ，それ以外の $6$ 通りについて $f(A) = 2$ です．よって，

  • $S_1 = 1^1\times 2 + 2^1\times 6 = 14,$
  • $S_2 = 1^2\times 2 + 2^2\times 6 = 26,$
  • $S_3 = 1^3\times 2 + 2^3\times 6 = 50,$
  • $S_4 = 1^4\times 2 + 2^4\times 6 = 98$

です．

サンプル2
入力
5 1 2
出力
1
1

サンプル3
入力
18392867552 14161132551 8
出力
726713581
100998767
286996549
468345593
527607776
620383472
238722459
972963401

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