P11405 [RMI 2020] 秘鲁 / Peru

译自 [8th Romanian Master of Informatics, RMI 2020](https://rmi.lbi.ro/rmi_2020/) D1T3。$\texttt{0.2s,0.25G}$。

**这是一道（函数式）交互题。** 有 $N$ 只甲虫在桌面上排成一行，从左到右编号为 $0\sim N-1$。第 $i$ 只甲虫的**体力**为 $S_i$。 每次可以选择**连续的**至多 $K$ 只甲虫，用 $E$ 的力量去击打它们。被击打的甲虫，若体力**不大于** $E$，则会死亡，否则无事发生。**死亡的甲虫会留在原地，可以击打死亡的甲虫。** 可以多次击打甲虫，每次 $E$ 的大小可以不同。 定义 $f(i)$ 为：杀死最左边的 $i$ 只甲虫，需要力量和的最小值。对于 $i=1,2,\cdots,N$，求出 $f(i)$。 为了减小输出量，你只需要求出 $\displaystyle \left(\sum_{1\le i\le N} f(i)\cdot 23^{N-i}\right)\bmod (10^9+7)$。 ### 实现细节 你不需要，也不应该实现 main 函数。 你需要实现以下的函数： ```cpp int solve(int N, int K, int S[]); ``` 交互库会调用 `solve` 函数恰好一次。参数的含义： - `N`：甲虫数量。 - `K`：一次击打最多击打的连续甲虫数。 - `S`：每只甲虫的体力。 返回一个整数表示 $\displaystyle \left(\sum_{1\le i\le N} f(i)\cdot 23^{N-i}\right)\bmod (10^9+7)$。

Sample grader 按照如下格式读取输入： 第一行，两个正整数 $N,K$； 第二行，$N$ 个正整数 $S_0,S_1,\cdots,S_{N-1}$。

Sample grader 输出一个整数，表示选手返回的答案。

#### 样例解释 $f$ 的值分别为 $3,3,9,12,12,20,23,23$。 #### 数据范围 对于 $100\%$ 的数据，保证： - $1\le K\le N\le 2.5\times 10^6$； - $1\le S_i\le 2\times 10^9$。 | 子任务编号 | $N,Q\le $ | 得分 | | :--: | :--: | :--: | | $ 1 $ | $ 2\times 10^3 $ | $18$ | | $ 2 $ | $ 4\times 10^5 $ | $31$ | | $ 3 $ | $ 2.5\times 10^6 $ | $51$ |