Disjoint Sparse Table による区間積 Python3編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
問題
長さ N の数列 A が与えられます。
Q 個のクエリが与えられるので順に解答してください。クエリの形式は以下の通りです。
・
l r：A_l × A_{l+1} × ... × A_{r-1} を 10^9 で割った余りを出力する。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N Q
A_0 A_1 ... A_{N-1}
l_1 r_1
l_2 r_2
...
l_Q r_Q
・1 行目には、数列の長さを表す整数 N とクエリの数を表す整数 Q が与えられます。
・2 行目には、数列 A が空白区切りで与えられます。
・続く Q 行の i 行目には i 個目のクエリが与えられます。クエリの形式は問題文の通りです。
・入力は合計で Q+2 行からなり、入力値最終行の末尾に改行が１つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
期待する出力は Q 行からなります。
i 行目には i 個目のクエリに対する答えを出力してください。
最後は改行し、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 10^5
・1 ≦ Q ≦ 10^5
・1 ≦ A_i ≦ 10^6
・0 ≦ l_i < r_i ≦ N
- 入力例1
-
5 3
36290 905630 1 723041 1
1 5
1 3
0 5
- 出力例1
-
807620830
905630
559920700
- 入力例2
-
15 10
113667 210874 432817 925667 728111 5000 823983 3240 1000000 19250 674616 417870 489209 276000 389363
0 1
9 15
6 9
0 7
9 14
4 11
9 13
8 15
9 11
6 15
- 出力例2
-
113667
320000000
920000000
912530000
640000000
0
189140000
0
986358000
0
