No.2661 Sweep Cards (Hard)
タグ : / 解いたユーザー数 6
作問者 : 👑
hamamu
/ テスター :
chineristAC
てんぷら
Note
This problem has an Easy version. The only differences from the Easy version are the parts in red text.
Problem Statement
There are $N$ cards numbered from $1$ to $N$.
The card with number $i$ written on it is called card $i$.
Initially, $N$ piles of cards are lined up in a row from left to right,
and the $i$-th pile from the left consists only of card $i$.
You may perform the following operation on this row of piles any number of times, $0$ or more.
- Choose a contiguous subsequence of length $K$ of the row of piles ($K$ is given in the input).
- Stack the chosen piles either in order from left to right so that the left one is on top, or in order from right to left so that the right one is on top.
Formal description of the operation (click to show details)
Represent each pile as a sequence $(a_1,a_2,\cdots,a_n)$ that lists the card numbers of the pile in order from the top.
Represent the row of piles as a sequence of sequences $A=(A_1,A_2,\cdots,A_m)$.
For sequences $X=(x_1,x_2,\cdots,x_{m'}),Y=(y_1,y_2,\cdots,y_{m''})$,
let $X+Y$ denote $(x_1,x_2,\cdots,x_{m'},y_1,y_2,\cdots,y_{m''})$.
Then, the operation is expressed as follows:
- Choose $2$ integers $L,R\ (1 \leq L < R \leq m)$ satisfying $R-L+1=K$.
- Replace $A$ with $(A_1,A_2,\dots,A_{L-1},A_L+A_{L+1}+\dots+A_R,A_{R+1},\dots,A_m)$ or $(A_1,A_2,\dots,A_{L-1},A_R+A_{R-1}+\dots+A_L,A_{R+1},\dots,A_m)$.
Description of the operation with concrete examples (click to show details)
Suppose there are $4$ piles, and the card numbers of each pile are as follows.
- The $1$-st pile from the left: $3,2,1$ in order from the top
- The $2$-nd pile from the left: only $4$
- The $3$-rd pile from the left: $5,6,7$ in order from the top
- The $4$-th pile from the left: only $8$
Let us denote this by (3,2,1),(4),(5,6,7),(8).
Examples of operations on this are as follows.
- Example 1: With $K=2$, choosing
(3,2,1),(4)and stacking them in order from left to right gives(3,2,1,4),(5,6,7),(8). - Example 2: With $K=3$, choosing
(4),(5,6,7),(8)and stacking them in order from right to left gives(3,2,1),(8,5,6,7,4).
For each $k=1,2,\cdots ,M$, find the number of card arrangements obtainable after performing operations until the number of piles becomes $X_k$, modulo $998244353$.
Here, 2 card arrangements are different if there exists a pair $(i,j)$ such that
"the $j$-th card from the top of the $i$-th pile from the left differs between the two, or exists in one and does not exist in the other".
Constraints
- All inputs are integers.
- $2 \le N \le$ $10^5$
- $2 \le K \le N$
- $1 \le M \le \min(N,10^5)$
- $1 \le X_1 \lt X_2 \lt \cdots \lt X_M \le N$
Input
The input is given from standard input in the following format.$N\ K\ M$ $X_1\ X_2\ \cdots \ X_M$
Output
For each $k=1,2,\cdots ,M$, print on the $k$-th line the number of card arrangements obtainable after performing operations until the number of piles becomes $X_k$, modulo $998244353$.
Print a newline at the end.
Sample
Sample 1
Input
5 3 4 1 2 3 5
Output
8 0 6 1
Let each pair of parentheses represent a pile, and the numbers inside represent the card numbers of the pile in order from the top.
For example, (3,2,1),(4),(5) means that
the card numbers of the $1$-st pile from the left are $3,2,1$ in order from the top,
and the $2$-nd and $3$-rd piles from the left consist of only the single card $4$ and $5$, respectively.
The initial arrangement is (1),(2),(3),(4),(5).
For example, (3,2,1),(4),(5) can be obtained by operating as follows.
- Choose the contiguous subsequence
(1),(2),(3)of length $3$ and stack it so that the right one is on top.(1),(2),(3),(4),(5)→(3,2,1),(4),(5)
Also, (5,2,3,4,1) can be obtained by operating as follows.
- Choose the contiguous subsequence
(2),(3),(4)of length $3$ and stack it so that the left one is on top.(1),(2),(3),(4),(5)→(1),(2,3,4),(5) - Choose the contiguous subsequence
(1),(2,3,4),(5)of length $3$ and stack it so that the right one is on top.(1),(2,3,4),(5)→(5,2,3,4,1)
There are $8$ card arrangements obtainable by operating until the number of piles becomes $X_1=1$, including the latter of the examples above.
There are $0$ card arrangements obtainable by operating until the number of piles becomes $X_2=2$.
There are $6$ card arrangements obtainable by operating until the number of piles becomes $X_3=3$, including the former of the examples above.
There is $1$ card arrangement obtainable by operating until the number of piles becomes $X_4=5$.
Sample 2
Input
6 3 6 1 2 3 4 5 6
Output
0 20 0 8 0 1
Sample 3
Input
100000 10 5 1 10 100 1000 10000
Output
766720650 955984556 280937557 323992730 243114217
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。