問題一覧 > 通常問題

No.3771 Leq-K Partition Multiplied

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

問題文

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

整数列 $A$ に対して，以下の問題の答えを $f(A)$ とします．

$A$ を空でない 連続 部分列に分割することを考えます． $A$ の各要素はちょうど $1$ つの部分列に属している必要があります． 全ての部分列について，現れる値の種類数が $K$ 以下となるように分割する際に，最小で何個の部分列に分割する必要があるか求めてください．

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

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

入力

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

出力

$N$ 行出力してください． $n$ 行目には $S_n$ を $998244353$ で割った余りを出力してください．

サンプル

サンプル1
入力
3 3 2 1
出力
3
9
33

$n=3$ の場合について考えます．

  • $(1,2,3)$ は， $(1,2), (3)$ のように $2$ 個の部分列に分割できます．
  • $(1,2,2)$ は， $(1,2,2)$ のように $1$ 個の部分列に分割できます．

$A$ として考えられるものは $3^3=27$ 通りありますが，そのうち $(1,2,3)$ の並び替え（ $6$ 通り）について $f(A) = 2$ ，それ以外（ $21$ 通り）について $f(A) = 1$ です． よって $S_3 = 6\times 2^1 + 21 \times 1^1 = 33$ です．

サンプル2
入力
4 2 3 2
出力
2
4
8
16

サンプル3
入力
10 122333444455555 3 9876543210
出力
595484111
116899793
297334529
660167065
603008404
232613563
68193567
936419468
625547368
48824042

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