問題一覧 > 通常問題

No.3770 Sum of Pow of Distinct Count

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

Problem Statement

You are given positive integers $N,M,K$.

For an integer sequence $A$, let $f(A)$ be the number of distinct values appearing in $A$.

There are $M^N$ possible integer sequences $A$ of length $N$ consisting of integers between $1$ and $M$, inclusive. Let $S_k$ be the sum of $f(A)^k$ over all of them.

For each $k = 1,2,\dots,K$, find $S_k$ modulo $998244353$.

Input

$N\ M\ K$
  • All input values are integers.
  • $1 \leq N \leq 10^{18}$
  • $1 \leq M \leq 10^{18}$
  • $1 \leq K \leq 2\times 10^5$

Output

Print $K$ lines. The $k$-th line should contain $S_k$ modulo $998244353$.

Sample

Sample 1
Input
3 2 4
Output
14
26
50
98

There are $2^3 = 8$ possible sequences $A$. Among them, $f(A) = 1$ for the $2$ sequences $(1,1,1)$ and $(2,2,2)$, and $f(A) = 2$ for the other $6$ sequences. Therefore,

  • $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$

.

Sample 2
Input
5 1 2
Output
1
1

Sample 3
Input
18392867552 14161132551 8
Output
726713581
100998767
286996549
468345593
527607776
620383472
238722459
972963401

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