問題一覧 > 通常問題

No.3139 Interval MEX ?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 : 👑 potato167
3 ProblemId : 12229 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-05-02 18:49:00

ストーリー

Interval XOR の XOR の部分を MEX にしただけの問題だしたろ！ → 解けず...

問題文

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

$0 \leq x\leq N$ を満たす整数 $x$ それぞれに対し、以下の条件をすべて満たす長さ $N$ の整数列 $A = (A_{0}, A_{1}, \dots, A_{N - 1})$ の個数を $998244353$ で割ったあまりを求めてください。

  • $0$ 以上 $N$ 未満の任意の整数 $i$ に対して、$0\leq A_{i}< i + M$
  • $\mathrm{MEX}(A) = x$

ただし、$\mathrm{MEX}(A)$ は $A$ に含まれない最小の非負整数とします。

制約

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

入力

$N\ M$

出力

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

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

サンプル

サンプル1
入力
3 1
出力
0
2
3
1

$x = 0$ のとき、条件を満たす $A$ は存在しないため、$1$ 行目には $0$ を出力します。

$x = 1$ のとき、$A = (0, 0, 0), (0, 0, 2)$ が条件を満たす全ての $A$ なので、$2$ 行目には $2$ を出力します。

$x = 2$ のとき、$A = (0, 0, 1), (0, 1, 0), (0, 1, 1)$ が条件を満たす全ての $A$ なので、$3$ 行目には $3$ を出力します。

$x = 3$ のとき、$A = (0, 1, 2)$ が条件を満たす全ての $A$ なので、$4$ 行目には $1$ を出力します。

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

$x = 3$ のとき、$A = (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0)$ が条件を満たす全ての $A$ なので、$4$ 行目には $4$ を出力します。

サンプル3
入力
16 7
出力
544441962
985238268
738928701
912248015
603387769
308480266
336860727
807140062
794986034
164296829
564886239
391995404
537273351
797530977
966069853
788146293
738575621

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