No.1172 Add Recursive Sequence

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.1172 Add Recursive Sequence

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 59
作問者 :

opt / テスター :

noshi91

19 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$ 項以降を，以下の漸化式で定めます:

$a_{i} = \sum_{k = 1}^{K} c_{k} a_{i - k} (i \geq K)$ ．

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

$($ 操作 $j)$ : $l_{j} \leq i < r_{j}$ なる各整数 $i$ に対し， $x_{i} \leftarrow x_{i} + a_{i - l_{j}}$ と更新する．

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

入力

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

 $K N M$ 
 $a_{0} a_{1} \dots a_{K - 1}$ 
 $c_{1} c_{2} \dots c_{K}$ 
 $l_{1} r_{1}$ 
 $l_{2} r_{2}$ 
 $⋮$ 
 $l_{M} 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} (0 \leq i < K)$
$0 \leq c_{i} \leq 10^{9} (1 \leq i \leq K)$
$0 \leq l_{j} < r_{j} \leq N (1 \leq j \leq M)$

出力

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

サンプル

サンプル1

入力

出力

数列 $(a_{i})_{i \geq 0}$ は漸化式 $a_{i} = a_{i - 1} + 2 a_{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

出力

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

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

yukicoder

No.1172 Add Recursive Sequence

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力