「DCOI」谜 官方题解

· · 题解

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。