311017: CF1921F. Sum of Progression
Description
You are given an array $a$ of $n$ numbers. There are also $q$ queries of the form $s, d, k$.
For each query $q$, find the sum of elements $a_s + a_{s+d} \cdot 2 + \dots + a_{s + d \cdot (k - 1)} \cdot k$. In other words, for each query, it is necessary to find the sum of $k$ elements of the array with indices starting from the $s$-th, taking steps of size $d$, multiplying it by the serial number of the element in the resulting sequence.
InputEach test consists of several testcases. The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of testcases. Next lines contain descriptions of testcases.
The first line of each testcase contains two numbers $n, q$ ($1 \le n \le 10^5, 1 \le q \le 2 \cdot 10^5$) — the number of elements in the array $a$ and the number of queries.
The second line contains $n$ integers $a_1, ... a_n$ ($-10^8 \le a_1, ..., a_n \le 10^8$) — elements of the array $a$.
The next $q$ lines each contain three integers $s$, $d$, and $k$ ($1 \le s, d, k \le n$, $s + d\cdot (k - 1) \le n$ ).
It is guaranteed that the sum of $n$ over all testcases does not exceed $10^5$, and that the sum of $q$ over all testcases does not exceed $2 \cdot 10^5 $.
OutputFor each testcase, print $q$ numbers in a separate line — the desired sums, separated with space.
ExampleInput5 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 2Output
5 1 3 -600000000 22 12 55 600000000 171 42 118 66 -108 23 2
Output
输入数据格式：
- 第一行包含一个整数 t，表示测试用例的数量。
- 每个测试用例的第一行包含两个整数 n 和 q，分别表示数组 a 的长度和查询的数量。
- 每个测试用例的第二行包含 n 个整数，表示数组 a 的元素。
- 接下来 q 行，每行包含三个整数 s, d, k，表示一个查询。
输出数据格式：
- 对于每个测试用例，输出 q 个整数，每个整数对应一个查询的结果，每个结果之间用空格分隔。
LaTeX 格式的公式：
给定数组 $ a $ 的长度为 $ n $，查询序列中的每个查询为 $ (s, d, k) $，需要计算的是：
$$
a_s + a_{s+d} \times 2 + a_{s+d \times 2} \times 3 + \dots + a_{s+d \times (k-1)} \times k
$$题目大意：给定一个数组和一个查询序列，每个查询包括三个参数 s, d, k。对于每个查询，计算数组中从第 s 个元素开始，每隔 d 个元素取一个，共取 k 个元素，按照取出的顺序分别乘以 1, 2, ..., k，然后求和。 输入数据格式： - 第一行包含一个整数 t，表示测试用例的数量。 - 每个测试用例的第一行包含两个整数 n 和 q，分别表示数组 a 的长度和查询的数量。 - 每个测试用例的第二行包含 n 个整数，表示数组 a 的元素。 - 接下来 q 行，每行包含三个整数 s, d, k，表示一个查询。 输出数据格式： - 对于每个测试用例，输出 q 个整数，每个整数对应一个查询的结果，每个结果之间用空格分隔。 LaTeX 格式的公式： 给定数组 $ a $ 的长度为 $ n $，查询序列中的每个查询为 $ (s, d, k) $，需要计算的是： $$ a_s + a_{s+d} \times 2 + a_{s+d \times 2} \times 3 + \dots + a_{s+d \times (k-1)} \times k $$