問題一覧 > 通常問題

No.2660 Sweep Cards (Easy)

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 10
作問者 : hamamu / テスター : chineristAC てんぷら
2 ProblemId : 10539 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-01 21:29:09

注意

本問題はHard版があります。Hard版と異なるのは赤文字の部分のみです。

問題文

11 から NN の番号がついた NN 枚のカードがあります。
番号 ii が書かれたカードをカード ii と呼びます。
はじめ、カードの山が NN 個左右一列に並んでおり、 左から ii 番目の山はカード ii のみからなっています。

あなたはこの山の列に対して、以下の操作を 00 回以上何度でも行えます。

  • 山の列の連続部分列で長さ KK (K=2)(K=2) のものを選ぶ（KK は入力で与えられる）
  • 選んだ山を左から右の順に左が上になるよう重ねる、または右から左の順に右が上になるよう重ねる
操作の形式的な説明（クリックすると詳細を表示します）

各山を、カード番号を山の上から順に並べた数列 (a1,a2,⋯ ,an)(a_1,a_2,\cdots,a_n) で表します。
山の列を、数列からなる列 A=(A1,A2,⋯ ,Am)A=(A_1,A_2,\cdots,A_m) で表します。
数列 X=(x1,x2,⋯ ,xm′),Y=(y1,y2,⋯ ,ym′′)X=(x_1,x_2,\cdots,x_{m'}),Y=(y_1,y_2,\cdots,y_{m''}) に対し、 X+YX+Y で (x1,x2,⋯ ,xm′,y1,y2,⋯ ,ym′′)(x_1,x_2,\cdots,x_{m'},y_1,y_2,\cdots,y_{m''}) を表します。
このとき、操作は以下のとおり表されます：

  • R−L+1=KR-L+1=K を満たす 22 つの整数 L,R (1≤L<R≤m)L,R\ (1 \leq L < R \leq m) を選ぶ
  • AA を (A1,A2,…,AL−1,AL+AL+1+⋯+AR,AR+1,…,Am)(A_1,A_2,\dots,A_{L-1},A_L+A_{L+1}+\dots+A_R,A_{R+1},\dots,A_m) または (A1,A2,…,AL−1,AR+AR−1+⋯+AL,AR+1,…,Am)(A_1,A_2,\dots,A_{L-1},A_R+A_{R-1}+\dots+A_L,A_{R+1},\dots,A_m) で置き換える

操作の具体例による説明（クリックすると詳細を表示します）

山が 44 つあり、各山のカード番号が以下のとおりだったとします。

  • 左から 11 番目の山：上から順に 3,2,13,2,1
  • 左から 22 番目の山：44 のみ
  • 左から 33 番目の山：上から順に 5,6,75,6,7
  • 左から 44 番目の山：88 のみ

これを(3,2,1),(4),(5,6,7),(8)と表すとします。
これに対する操作例は以下のとおりです。

  • 操作例1：K=2K=2 で、(3,2,1),(4)を選び、左から右の順に重ねると、(3,2,1,4),(5,6,7),(8)になります。
  • 操作例2：K=3K=3 で、(4),(5,6,7),(8)を選び、右から左の順に重ねると、(3,2,1),(8,5,6,7,4)になります。


k=1,2,⋯ ,Mk=1,2,\cdots ,M について、山の個数が XkX_k になるまで操作した後得られるカード配置の個数を 109+710^9+7 で割った余りを求めてください。
ここで、ある2つのカード配置が異なるとは、 「左から ii 番目の山の上から jj 番目のカードが、両者で異なる、または一方に存在しもう一方に存在しない」 を満たす (i,j)(i,j) が存在することを意味します。

制約

  • 入力は全て整数
  • 2≤N≤2 \le N \le 10710^7
  • K=2K=2
  • 1≤M≤min⁡(N,105)1 \le M \le \min(N,10^5)
  • 1≤X1<X2<⋯<XM≤N1 \le X_1 \lt X_2 \lt \cdots \lt X_M \le N

入力

以下の形式で標準入力から与えられます。 
N K MN\ K\ M
X1 X2 ⋯ XMX_1\ X_2\ \cdots \ X_M

出力

k=1,2,⋯ ,Mk=1,2,\cdots ,M について、kk 行目に、山の個数が XkX_k になるまで操作した後得られるカード配置の個数を 109+710^9+7 で割った余りを出力してください。
最後に改行してください。

サンプル

サンプル1
入力
4 2 3
1 2 4
出力
22
16
1

括弧が各山を、括弧内の数値が山のカード番号を上から順に表すとします。
例えば、(3,2,1),(4)は、 左の山のカード番号が上から順に 3,2,13,2,1 であり、右の山はカード 44 の一枚のみ、を表します。
初期配置は(1),(2),(3),(4)です。

例えば次のように操作することで(3,2,1),(4)になります。

  • 長さ 22 の連続部分列(2),(3)を選び、右が上になるよう重ねる。 (1),(2),(3),(4) → (1),(3,2),(4)
  • 長さ 22 の連続部分列(1),(3,2)を選び、右が上になるよう重ねる。 (1),(3,2),(4) → (3,2,1),(4)

また、次のように操作することで(1),(4,2,3)になります。

  • 長さ 22 の連続部分列(2),(3)を選び、左が上になるよう重ねる。 (1),(2),(3),(4) → (1),(2,3),(4)
  • 長さ 22 の連続部分列(2,3),(4)を選び、右が上になるよう重ねる。 (1),(2,3),(4) → (1),(4,2,3)

山の個数が X1=1X_1=1 個になるまで操作して得られるカード配置は、2222 個あります。
山の個数が X2=2X_2=2 個になるまで操作して得られるカード配置は、上記例を含め 1616 個あります。
山の個数が X3=4X_3=4 個になるまで操作して得られるカード配置は、11 個です。

サンプル2
入力
2 2 2
1 2
出力
2
1
サンプル3
入力
16 2 1
1
出力
937603017

109+710^9+7 で割った余りを出力することにご注意ください。

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