問題一覧 > 通常問題

No.1172 Add Recursive Sequence

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 51
作問者 : optopt / テスター : noshi91noshi91
16 ProblemId : 4271 / 出題時の順位表
問題文最終更新日: 2020-12-04 09:43:15

問題文

整数列 $(a_i)_{i \geq 0}$ の最初の $K$ 項 $a_0,\dots, a_{K-1}$ と,$K$ 個の整数 $c_1, \dots,c_K$ が与えられます. $(a_i)_{i \geq 0}$ の第 $K$ 項以降を,以下の漸化式で定めます:

  • $\displaystyle a_i = \sum_{k=1}^K c_k a_{i-k} \quad (i \geq K)$.

長さ $N$ の配列 $(x_0, \dots, x_{N-1})$ の全要素を $0$ に初期化し,以下の操作 $j = 1,\dots, M$ を,操作 $1$ から順に行います:

  • $($操作 $j)$:$\quad l_j \leq i < r_j$ なる各整数 $i$ に対し,$x_i \gets x_i + a_{i-l_j}$ と更新する.

各整数 $i$ $(0 \leq i < N)$ に対し,全ての操作の後の $x_i$ の値を $10^9 + 7$ で割った余りを求めてください.

入力

入力は以下の形式で与えられる:

$K \quad N \quad M$
$a_0 \quad a_1 \quad \cdots \quad a_{K-1}$
$c_1 \quad c_2 \quad \cdots \quad c_K$
$l_1 \quad r_1$
$l_2 \quad r_2$
$\ \vdots$
$l_M \quad r_M$
  • 入力は全て整数
  • $1 \leq K \leq 200$
  • $1 \leq N \leq 10^5$
  • $1 \leq M \leq 10^5$
  • $0 \leq a_i \leq 10^9 \quad (0 \leq i < K)$
  • $0 \leq c_i \leq 10^9 \quad (1 \leq i \leq K)$
  • $0 \leq l_j < r_j \leq N \quad (1 \leq j \leq M)$

出力

$(i+1)$ 行目 $(0 \leq i < N)$ に,全ての操作の後の $x_i$ の値を $10^9 + 7$ で割った余りを出力せよ. 最後に改行を出力すること.

サンプル

サンプル1
入力
2 6 3
3 1
1 2
2 4
0 5
3 6
出力
3
1
10
13
24
7

数列 $(a_i)_{i \geq 0}$ は漸化式 $a_i = a_{i-1} + 2a_{i-2}$ を満たし,

  • $a_0 = 3$
  • $a_1 = 1$
  • $a_2 = 7$
  • $a_3 = 9$
  • $a_4 = 23$
となります.

配列 $(x_0,x_1,x_2,x_3,x_4,x_5)$ は,

  • 操作 $1$ の後: $(0, 0, 3, 1, 0, 0)$
  • 操作 $2$ の後: $(3, 1, 10, 10, 23, 0)$
  • 操作 $3$ の後: $(3, 1, 10, 13, 24, 7)$
となるため,上のような出力になります.

サンプル2
入力
4 10 6
38357 29371 11020 79402
86940 11636 45261 69281
2 8
1 9
5 6
2 7
0 6
3 10
出力
38357
67728
117105
187521
18341484
711694633
729776525
364121460
472238231
652635015

$10^9 + 7$ で割った余りを出力してください.

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