No.3139 Interval MEX ?
タグ : / 解いたユーザー数 8
作問者 : 👑
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もしくは右上の雲マークをクリックしてアカウントを作成してください。