CF1921F Sum of Progression

给定一个长度为 $n$ 的数组 $a$。还有 $q$ 个查询，每个查询的形式为 $s, d, k$。 对于每个查询 $q$，请计算 $a_s + a_{s+d} \cdot 2 + \dots + a_{s + d \cdot (k - 1)} \cdot k$ 的和。换句话说，对于每个查询，需要找到从第 $s$ 个元素开始，每次步长为 $d$，共取 $k$ 个元素，并将第 $i$ 个取到的元素乘以 $i$，然后求和。

每个测试点包含若干组测试数据。第一行包含一个整数 $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, \ldots, a_n$（$-10^8 \le a_1, \ldots, 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$ 个数，表示每个查询的答案，数之间用空格隔开，每组测试数据输出一行。

由 ChatGPT 4.1 翻译