No.2660 Sweep Cards (Easy)
タグ : / 解いたユーザー数 10
作問者 :
hamamu
/ テスター :
chineristAC
てんぷら
注意
本問題はHard版があります。Hard版と異なるのは赤文字の部分のみです。
問題文
$1$ から $N$ の番号がついた $N$ 枚のカードがあります。
番号 $i$ が書かれたカードをカード $i$ と呼びます。
はじめ、カードの山が $N$ 個左右一列に並んでおり、
左から $i$ 番目の山はカード $i$ のみからなっています。
あなたはこの山の列に対して、以下の操作を $0$ 回以上何度でも行えます。
- 山の列の連続部分列で長さ $K$ $(K=2)$ のものを選ぶ（$K$ は入力で与えられる）
- 選んだ山を左から右の順に左が上になるよう重ねる、または右から左の順に右が上になるよう重ねる
操作の形式的な説明（クリックすると詳細を表示します）
各山を、カード番号を山の上から順に並べた数列 $(a_1,a_2,\cdots,a_n)$ で表します。
山の列を、数列からなる列 $A=(A_1,A_2,\cdots,A_m)$ で表します。
数列 $X=(x_1,x_2,\cdots,x_{m'}),Y=(y_1,y_2,\cdots,y_{m''})$ に対し、
$X+Y$ で $(x_1,x_2,\cdots,x_{m'},y_1,y_2,\cdots,y_{m''})$ を表します。
このとき、操作は以下のとおり表されます：
- $R-L+1=K$ を満たす $2$ つの整数 $L,R\ (1 \leq L < R \leq m)$ を選ぶ
- $A$ を $(A_1,A_2,\dots,A_{L-1},A_L+A_{L+1}+\dots+A_R,A_{R+1},\dots,A_m)$ または $(A_1,A_2,\dots,A_{L-1},A_R+A_{R-1}+\dots+A_L,A_{R+1},\dots,A_m)$ で置き換える
操作の具体例による説明（クリックすると詳細を表示します）
山が $4$ つあり、各山のカード番号が以下のとおりだったとします。
- 左から $1$ 番目の山：上から順に $3,2,1$
- 左から $2$ 番目の山：$4$ のみ
- 左から $3$ 番目の山：上から順に $5,6,7$
- 左から $4$ 番目の山：$8$ のみ
これを(3,2,1),(4),(5,6,7),(8)と表すとします。
これに対する操作例は以下のとおりです。
- 操作例1：$K=2$ で、
(3,2,1),(4)を選び、左から右の順に重ねると、(3,2,1,4),(5,6,7),(8)になります。 - 操作例2：$K=3$ で、
(4),(5,6,7),(8)を選び、右から左の順に重ねると、(3,2,1),(8,5,6,7,4)になります。
$k=1,2,\cdots ,M$ について、山の個数が $X_k$ になるまで操作した後得られるカード配置の個数を $10^9+7$ で割った余りを求めてください。
ここで、ある2つのカード配置が異なるとは、
「左から $i$ 番目の山の上から $j$ 番目のカードが、両者で異なる、または一方に存在しもう一方に存在しない」
を満たす $(i,j)$ が存在することを意味します。
制約
- 入力は全て整数
- $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$
入力
以下の形式で標準入力から与えられます。$N\ K\ M$ $X_1\ X_2\ \cdots \ X_M$
出力
$k=1,2,\cdots ,M$ について、$k$ 行目に、山の個数が $X_k$ になるまで操作した後得られるカード配置の個数を $10^9+7$ で割った余りを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
4 2 3 1 2 4
出力
22 16 1
括弧が各山を、括弧内の数値が山のカード番号を上から順に表すとします。
例えば、(3,2,1),(4)は、
左の山のカード番号が上から順に $3,2,1$ であり、右の山はカード $4$ の一枚のみ、を表します。
初期配置は(1),(2),(3),(4)です。
例えば次のように操作することで(3,2,1),(4)になります。
- 長さ $2$ の連続部分列
(2),(3)を選び、右が上になるよう重ねる。(1),(2),(3),(4)→(1),(3,2),(4) - 長さ $2$ の連続部分列
(1),(3,2)を選び、右が上になるよう重ねる。(1),(3,2),(4)→(3,2,1),(4)
また、次のように操作することで(1),(4,2,3)になります。
- 長さ $2$ の連続部分列
(2),(3)を選び、左が上になるよう重ねる。(1),(2),(3),(4)→(1),(2,3),(4) - 長さ $2$ の連続部分列
(2,3),(4)を選び、右が上になるよう重ねる。(1),(2,3),(4)→(1),(4,2,3)
山の個数が $X_1=1$ 個になるまで操作して得られるカード配置は、$22$ 個あります。
山の個数が $X_2=2$ 個になるまで操作して得られるカード配置は、上記例を含め $16$ 個あります。
山の個数が $X_3=4$ 個になるまで操作して得られるカード配置は、$1$ 個です。
サンプル2
入力
2 2 2 1 2
出力
2 1
サンプル3
入力
16 2 1 1
出力
937603017
$10^9+7$ で割った余りを出力することにご注意ください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。