自动搬运

查看原文

来自洛谷，原作者为

	言琢დ “我会成为这里的主宰，清除掉整片土地上的一切障碍，只留下我跟那一堆白骨，她永远不朽，而我不死不灭。”

搬运于2025-08-24 22:33:19，当前版本为作者最后更新于2021-08-16 22:19:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

upd on 2021.10.15：补充了一份理性的证明。

一篇来自出题人的官方题解。

$$\large\text{「DCOI」谜}$$ $$\large\rm\text{言琢დ}$$ $$\large 2021.08.13$$

样例含义

2676 1930
5148 3667
5453 4764
16734806 16332913
26943973 33293903 

将样例二复制下来，每四个数字一组：2676 1930 5148 3667 5453 4764 1673 4806 1633 2913 2694 3973 3329 3903。

考虑使用区位码表示，结果为：红尘有你终相伴 笑傲江湖情两牵。

很遗憾赛时/讲评前未能有同学猜中含义，没有同学获得奖励。

题目解法

数据范围中 $K\le 2N-1$ 提示了正解。

考虑从 $(N,N)$ 开始，波浪形向左遍历，这样的方案一定是不劣的。

即：$(N,N)\rightarrow(N-1,N-1)\rightarrow(N,N-1)\rightarrow(N-1,N-2)\rightarrow\dots$

此时计算答案仅需对数字三角形中最后两行计算数字和即可。

需要注意，对于 $100\%$ 的数据需要分步取模。

分步取模

根据求和公式 $s=\dfrac{n\times(l+r)}{2}$，其中 $l,r$ 表示首项、末项，$n$ 表示项数。

其中 $n$ 和 $(l+r)$ 必有一项为偶数（否则 $s$ 一定不是整数），可以考虑找到这个偶数先 $÷2$，再与另一个数作乘法并取模。

另一种常见办法是使用 逆元，找到 $2$ 关于 $10^9+7$ 的逆元，乘上逆元即为除去它本身。

证明

这里出题人补充一种较为理性的证法。

证明：考虑设我们以此种方式遍历到的数依次为

$$a_1,a_2,\dots,a_K$$

我们将序列 $a$ 进行分类，分为位于倒数第二行的序列 $b_{K/2}$ 和位于倒数第一行的序列 $c_{K-K/2}$。

其中：

$$\begin{aligned}b_i&=a_{2i}\\c_i&=a_{2i-1}\end{aligned} $$

以上的设法和考虑都是显而易见的。

我们考虑反证，假如我们遍历到一个更优的序列 $d$：

$$d_1,d_2,\dots,d_K$$

将它与序列 $a$ 作比较，那么序列 $d$ 必须至少存在一个位置 $x$，满足：

$$d_x\not\in a$$

另外这个元素至少要比序列 $a$ 中的最小元素大，理由是

$$\sum_{i=1}^{K}d_i>\sum_{i=1}^{K}a_i$$

考虑联立 $d_x$ 不在序列 $a$ 中和 $d_x>\min\{a\}$ 这两个条件。

首先根据前者，我们知道 $d_x<\min\{c\}$。

那么得到 $d_x$ 必须大于 $\min\{b\}$。

而 $b$ 中元素取的是倒数第二行最大的 $\left\lfloor\dfrac{K}{2}\right\rfloor$ 个元素。

所以 $d_x$ 就必须在倒数第一行中剩下的元素中取。

然后到这里就可以用到一个结论：

波浪形向左遍历，是遍历到倒数第一行中剩下元素的最快方法。

这个结论根据图示是很明显的。

据此我们得到：如果想要得到 $d_x$，就必须舍弃更优的一些解。

所以假设不成立，我们得不到更优的 $d_x$，从而也就得不到更优的序列 $d$。