← 返回题目列表

Codeforces · 1921/F

F. 级数总和

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

给你一个由 $$$n$$$ 数字组成的数组 $$$a$$$。还有 $$$q$$$ 形式的 $$$s、d、k$$$ 查询。

对于每个查询 $$$q$$$,求元素 $$$a_s + a_{s+d} \cdot 2 + \dots + a_{s + d \cdot (k - 1)} \cdot k$$$ 的总和。换句话说,对于每个查询,需要找到数组中 $$$k$$$ 元素的总和,索引从 $$$s$$$ 开始,步长为 $$$d$$$,将其乘以结果序列中元素的序列号。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。接下来的几行包含测试用例的描述。

每个测试用例的第一行包含两个数字 $$$n, q$$$ ($$$1 \le n \le 10^5, 1 \le q \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 中的元素数量和查询数量。

第二行包含 $$$n$$$ 整数 $$$a_1, ... a_n$$$ ($$$-10^8 \le a_1, ..., a_n \le 10^8$$$) — 数组 $$$a$$$ 的元素。

接下来的 $$$q$$$ 行每行包含三个整数 $$$s$$$、$$$d$$$ 和 $$$k$$$ ($$$1 \le s, d, k \le n$$$, $$$s + d\cdot (k - 1) \le n$$$ )。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$,并且所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10^5 $$$。

输出

对于每个测试用例,在单独的行中打印 $$$q$$$ 数字 - 所需的总和,用空格分隔。

示例

输入 #1

5
3 3
1 1 2
1 2 2
2 2 1
1 1 2
3 1
-100000000 -100000000 -100000000
1 1 3
5 3
1 2 3 4 5
1 2 3
2 3 2
1 1 5
3 1
100000000 100000000 100000000
1 1 3
7 7
34 87 5 42 -44 66 -32
2 2 2
4 3 1
1 3 2
6 2 1
5 2 2
2 5 2
6 1 2

输出 #1

5 1 3 
-600000000 
22 12 55 
600000000 
171 42 118 66 -108 23 2