← 返回题目列表

AtCoder · past19_n

N. 有限幂级数

中文机器翻译题面 查看原题

问题陈述

给你一个长度-N 序列 A=(A _ 1,A _ 2,\ldots,A _ N) 非负整数和实数值 x 严格大于 0 且小于或等于 1.

对于整数对 (l,r)\ (1\leq l\leq r\leq N),我们定义 f(l,r) 如下:

\begin{aligned}f(l,r)&=A _ l+A _ {l+1}x+A _ {l+2}x ^ 2+\cdots+A _ {r}x ^ {r-l}\\&=\sum _ {i=0} ^ {r - l}A _ {i+l}x ^ i.\end{aligned}

答案 Q 查询。 在 i第一个查询 (1\leq i\leq Q),给定一个整数对 (l _ i,r _ i)\ (1\leq l _ i\leq r _ i\leq N),查找 f(l _ i,r _ i).

约束

  • 1\leq N\leq2\times10 ^ 5
  • 0\leq A _ i\leq10 ^ 9\ (1\leq i\leq N)
  • 0\lt x\leq 1
  • 1\leq Q\leq2\times10 ^ 5
  • 1\leq l _ i\leq r _ i\leq N\ (1\leq i\leq Q)
  • N,A _ i,Q,l _ i,和 r _ i 是整数。
  • x 是一个实际值,最多 15 小数位。

输入

输入由标准输入按以下格式给出:

N
A _ 1 A _ 2 \ldots A _ N
x
Q
l _ 1 r _ 1
l _ 2 r _ 2
\vdots
l _ Q r _ Q

输出

打印 Q 行。 的 i第行 (1\leq i\leq Q) 应包含该值 f(l _ i,r _ i) 为 i第一个查询 (l _ i,r _ i)。 如果与真实值的相对或绝对误差最多为,则您的答案被认为是正确的 10 ^ {-6}.


示例输入 1

7
3 1 4 1 5 9 2
0.25
4
1 3
3 6
1 7
2 2

示例输出 1

3.5
4.703125
3.54443359375
1

对于每个查询,答案如下。

  • f(1,3)=A _ 1\times0.25 ^ 0+A _ 2\times0.25 ^ 1+A _ 3\times0.25 ^ 2=3+0.25+0.25=3.5.
  • f(3,6)=A _ 3\times0.25 ^ 0+A _ 4\times0.25 ^ 1+A _ 5\times0.25 ^ 2+A _ 6\times0.25 ^ 3=4+0.25+0.3125+0.140625=4.703125.
  • f(1,7)=A _ 1\times0.25 ^ 0+A _ 2\times0.25 ^ 1+A _ 3\times0.25 ^ 2+A _ 4\times0.25 ^ 3+A _ 5\times0.25 ^ 4+A _ 6\times0.25 ^ 5+A _ 7\times0.25 ^ 6=3+0.25+0.25+0.015625+0.01953125+0.0087890625+0.00048828125=3.54443359375.
  • f(2,2)=A _ 2\times0.25 ^ 0=1.

因为如果相对或绝对误差最多为,则您的答案被认为是正确的 10 ^ {-6},输出如下

3.5
4.703125
3.54443359375
0.999999

和

3.4999965
4.703129703125
3.54443004931640625
1.000001

也被接受。


示例输入 2

15
6 45 81 83 28 40 31 30 51 31 59 50 94 36 0
0.998244353
20
1 2
1 5
1 10
2 5
2 10
3 3
3 8
3 12
4 4
4 14
5 5
5 11
5 13
5 14
6 7
7 7
8 10
10 13
10 14
12 14

示例输出 2

50.920995885
242.004326432639783195178618854259
422.764240065920208662445303267128
236.419395434977014285377699356
417.497217803865912440022892137641
81
292.066191815728552247199317241863
480.544234637661958884554506013369
83
528.144974561396676686531955107577
28
268.416129630805326045766513470066
410.492717775411750526215653552396
445.927866482402907904585917660160
70.945574943
31
111.801707440188046879
233.226782486727123857410847838
268.974634315843968519190799533618
179.708673560669989924