证明

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

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

\[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\)。

题目解法

数据范围中 \(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\) 的逆元，乘上逆元即为除去它本身。

样例含义

2676 1930
5148 3667
5453 4764
16734806 16332913
26943973 33293903

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

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

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