問題一覧 > 通常問題

No.2660 Sweep Cards (Easy)

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 10
作問者 : 👑 hamamu / テスター : chineristAC てんぷら
お気に入りにしたユーザー ProblemId : 10539 / 自分の提出
問題文最終更新日: 2024-03-01 21:29:09
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 419 (順位表) の他の問題:

Note

This problem has a Hard version. It differs from the Hard version only in the parts written 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 arranged 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$ $(K=2)$ 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 by the sequence $(a_1,a_2,\cdots,a_n)$ that lists its card numbers in order from the top of the pile.
Represent the row of piles by the list 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 by concrete examples (click to show details)

Suppose there are $4$ piles and the card numbers in each pile are as follows.

  • $1$-st pile from the left: $3,2,1$ in order from the top
  • $2$-nd pile from the left: only $4$
  • $3$-rd pile from the left: $5,6,7$ in order from the top
  • $4$-th pile from the left: only $8$

We denote this by (3,2,1),(4),(5,6,7),(8).
Examples of operations on this are as follows.

  • Example operation 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 operation 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 that can be obtained after performing operations until the number of piles becomes $X_k$, modulo $10^9+7$.
Here, two card arrangements are said to be 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^7$
  • $K=2$
  • $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 that can be obtained after performing operations until the number of piles becomes $X_k$, modulo $10^9+7$.
Print a newline at the end.

Sample

Sample 1
Input
4 2 3
1 2 4
Output
22
16
1

Each pair of parentheses represents a pile, and the numbers inside represent the card numbers of the pile in order from the top.
For example, (3,2,1),(4) means that the left pile has card numbers $3,2,1$ in order from the top, and the right pile consists of the single card $4$.
The initial arrangement is (1),(2),(3),(4).

For example, the following operations result in (3,2,1),(4).

  • Choose the contiguous subsequence (2),(3) of length $2$ and stack them so that the right one is on top. (1),(2),(3),(4) → (1),(3,2),(4)
  • Choose the contiguous subsequence (1),(3,2) of length $2$ and stack them so that the right one is on top. (1),(3,2),(4) → (3,2,1),(4)

Also, the following operations result in (1),(4,2,3).

  • Choose the contiguous subsequence (2),(3) of length $2$ and stack them so that the left one is on top. (1),(2),(3),(4) → (1),(2,3),(4)
  • Choose the contiguous subsequence (2,3),(4) of length $2$ and stack them so that the right one is on top. (1),(2,3),(4) → (1),(4,2,3)

There are $22$ card arrangements that can be obtained by performing operations until the number of piles becomes $X_1=1$.
There are $16$ card arrangements, including the examples above, that can be obtained by performing operations until the number of piles becomes $X_2=2$.
There is $1$ card arrangement that can be obtained by performing operations until the number of piles becomes $X_3=4$.

Sample 2
Input
2 2 2
1 2
Output
2
1
Sample 3
Input
16 2 1
1
Output
937603017

Note that you should print the remainder modulo $10^9+7$.

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