P16374 [IATI 2026] Arithmetic Progression

Sashka 有一个由 $N$ 个正整数构成的序列 $A_0,A_1,\dots,A_{N-1}$，一个正整数 $K$，以及一个等差数列（序列 $P_0, P_1,\dots$ 是等差数列当且仅当存在常数 $D$ 使得对所有 $i \geq 1$ 有 $P_i = D + P_{i-1}$），该数列由其首项 $S$ 和相邻两项之差 $D$ 定义，且 $S$ 与 $D$ 均为正整数。 她关心的是 $A$ 的长度为 $K$ 的子序列（从一个序列中删去零个或多个元素，但不改变剩余元素的顺序，所得到的序列称为该序列的子序列），记作 $B_0, B_1,\dots,B_{K-1}$。 请编写一个程序 $\texttt{arithmetic\_progression}$，计算这样的子序列与等差数列的前 $K$ 项对应相乘之和的最小值，即最小化如下求和式： $$\sum_{i=0}^{K-1} B_i \times (S + i \times D)$$ ### 实现细节 你需要实现函数 `solve`： ```cpp __int128 solve(std::vector A, int K, long long S, int D) ``` - $A$：向量，包含 $A_0,A_1, \dots, A_{N-1}$ - $K$：子序列的长度 - $S$：等差数列的首项 - $D$：等差数列的公差 你的函数应返回上述类型的最小可能和。由于结果可能非常大，你的函数应返回非标准的 `__int128` 类型（128 位整数）。头文件 `arithmetic_progression.h` 中包含了针对 `` 运算符的重载定义，允许对 `__int128` 变量使用 `std::cin`、`std::cout` 和 `std::cerr`。

输入格式： - 第 1 行：$N$ $K$ $S$ $D$； - 第 2 行：$A_0\ A_1\ A_2\ ...\ A_{N-1}$。

输出格式： - 第 1 行：一个整数，等于 `solve` 返回的答案。

### 样例 1 解释 等差数列为 $\{1,2\}$。我们选择 $B=\{5,1\}$，得到最优结果：$5 \times 1 + 1 \times 2 = 7$。 ### 样例 2 解释 等差数列为 $\{6,7\}$。我们选择 $B=\{1,4\}$，得到最优结果：$1 \times 6 + 4 \times 7 = 34$。 ### 样例 3 解释 等差数列为 $\{4,10,16,22\}$。我们选择 $B=\{18,12,8,11\}$，得到最优结果：$18 \times 4 + 12 \times 10 + 8 \times 16 + 11 \times 22 = 562$。 ### 数据范围 - $1 \leq K \leq N \leq 300\ 000$ - $1 \leq D \leq 10^9$ - $1 \leq A_i, S \leq 10^{15}$ ### 子任务 | **子任务** | **分值** | **依赖的子任务** | **$N$** | **其他限制** | | :---: | :---: | :---: | :---: | :---: | | $0$ | $0$ | $-$ | $-$ | 样例测试。 | | $1$ | $5$ | $0$ | $\leq 20$ | $-$ | | $2$ | $6$ | $0-1$ | $\leq 500$ | $-$ | | $3$ | $3$ | $0-2$ | $\leq 3\ 000$ | $-$ | | $4$ | $1$ | $-$ | $\leq 100\ 000$ | $K = N$ | | $5$ | $4$ | $4$ | $\leq 100\ 000$ | $K \geq N - 1$ | | $6$ | $4$ | $4-5$ | $\leq 100\ 000$ | $K \geq N-2$ | | $7$ | $5$ | $-$ | $\leq 100\ 000$ | $A$ 是通过均匀随机打乱由作者为该测试点选定的某个序列 $T$ 得到的。 | | $8$ | $5$ | $0-7$ | $\leq 100\ 000$ | $-$ | | $9$ | $67$ | $0-8$ | $\leq 300\ 000$ | $-$ | 一个子任务的分数仅当该子任务及其所依赖子任务的全部测试数据均成功通过时才能获得。 翻译由 DeepSeek V4 Pro 完成