問題一覧 > 通常問題

No.3139 Interval MEX ?

レベル : / AI推定難易度 : 2525 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 8
作問者 : 👑 potato167
お気に入りにしたユーザー ProblemId : 12229 / 自分の提出
問題文最終更新日: 2025-05-02 18:49:00
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 466 オムニバスコンテスト (順位表) の他の問題:

Story

I'll set a problem that just replaces the XOR part of Interval XOR with MEX! → Couldn't solve it...

Problem Statement

You are given positive integers $N, M$.

For each integer $x$ satisfying $0 \leq x\leq N$, find the number, modulo $998244353$, of integer sequences $A = (A_{0}, A_{1}, \dots, A_{N - 1})$ of length $N$ that satisfy all of the following conditions.

  • For every integer $i$ that is at least $0$ and less than $N$, $0\leq A_{i}< i + M$
  • $\mathrm{MEX}(A) = x$

Here, $\mathrm{MEX}(A)$ is the smallest non-negative integer not contained in $A$.

Constraints

  • $1\leq N\leq 5\times 10^{5}$
  • $1\leq M\leq 5\times 10^{5}$
  • All inputs are integers

Input

$N\ M$

Output

Output $N + 1$ lines.

On line $i + 1$, output the answer for $x = i$.

Sample

Sample 1
Input
3 1
Output
0
2
3
1

When $x = 0$, no $A$ satisfies the conditions, so output $0$ on line $1$.

When $x = 1$, $A = (0, 0, 0), (0, 0, 2)$ are all the $A$ satisfying the conditions, so output $2$ on line $2$.

When $x = 2$, $A = (0, 0, 1), (0, 1, 0), (0, 1, 1)$ are all the $A$ satisfying the conditions, so output $3$ on line $3$.

When $x = 3$, $A = (0, 1, 2)$ is the only $A$ satisfying the conditions, so output $1$ on line $4$.

Sample 2
Input
3 2
Output
6
6
8
4

When $x = 3$, $A = (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0)$ are all the $A$ satisfying the conditions, so output $4$ on line $4$.

Sample 3
Input
16 7
Output
544441962
985238268
738928701
912248015
603387769
308480266
336860727
807140062
794986034
164296829
564886239
391995404
537273351
797530977
966069853
788146293
738575621

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