CF1852A 中的结论证明

Foreword

今天比赛在 CF1852A 卡了很久，虽然最终没能想出官方题解中给出的逆向计算法，但是却意外地发掘出了一个有趣的性质，在这里给出其证明。

Preliminary

我们定义字符串 $S$（下标从 $1$ 开始）拥有周期 $k\in (0,|S|) \cap \Z$ 当且仅当 $\forall i \in [1,|S|-k],\ S[i]=S[i+k]$。记 $\text{per}(S)$ 为 $S$ 的最小周期。特别的，若 $S$ 没有周期，则 $\text{per}(S)=|S|$。

记字符串的子串为 $S[i,j]=S[i,j+1)=S(i-1.j]=S(i-1,j+1)$。

Introduction

原题面的数学模型如下

给出一个长度为 $n$ 的数组 $\{a_i\}\subset \N$ 满足 $0\lt a_1 \lt a_2 \lt .. \lt a_n$。定义 $\text{M}(E,i)$ 为离散集合 $E$ 中第 $i$ 小的数，且 $E_0=\N_{+}$，$E_i=E_{i-1}-\left\{\ \text{M}(E_{i-1},a_j)\ :\ j \in [1,n]\cap\Z\ \right\}$，求 $\min E_k$。

若 $a_1 > 1$，则 $\min E_k=1$。在之后的讨论中，我们默认 $a_1=1$。此外，出于一致性考虑，不妨令 $a_{n+1}=+\infty$。

很显然，对于任意的 $s\in \N_{+}$，存在 $u_s\in \N$，使得 $s\in E_{u_s}$ 且 $s\notin E_{u_s+1}$。由定义，$\exist\,v_s \in [1,n]\cap\Z \text{ s.t. }\text{M}(E_{u_s},a_{v_s})=s$。由此可以定义这样一个无限长的字符串 $T$ 满足 $T[s]=v_s$。我们有以下结论

以及

即 $T(a_i-i,a_i]$ 中每个字符只出现了一次。

例如，若我们令 $1,2,3,..$ 编码的字符为 $\texttt{a},\texttt{b},\texttt{c},..$，对于 $\{a_i\}=\lt 1, 4\gt$，$T[1,30]=\texttt{aaabababababababababababababab}$；对于 $\{a_i\}=\lt 1, 2, 8, 9, 13, 25\gt$，$T[1,30]=\texttt{abababacdbacedbacedbacedfbaced}$。

Proof(Maybe)

我们尝试使用归纳证明的思想证明上述结论。首先，当 $n=1$ 时这一结论显然成立。现在不妨假设 $n=k-1$ 时结论成立，此时不难发现将 $a_k$ 加入到数组（此时 $a_{k+1}$ 变为 $+\infty$）对于 $T[1,a_k)$ 没有影响。考虑到 $\text{per}(T(a_{k-1}-k+1,a_k))=k-1$，我们可以推得 $T(a_k-k,a_k)$ 中每个字符只出现了一次，且这些字符在 $[1,k-1]$ 之间。注意到 $T[a_k]=k$，故 $T(a_k-k,a_k]$ 中每个字符只出现了一次。

而注意到 $\forall t\isin \N$，$E_{t+1}$ 相较于 $E_t$ 少了 $k$ 个数，第 $a_k$ 小的数也就往后顺延了 $k$ 位（注意，此时 $a_{k+1}=\infty$，故而这 $k$ 位都是连续的），故而 $\text{M}(E_{t+1},a_k)=\text{M}(E_t,a_k)+k$，亦 $T[a_k]=T[a_k+k]=T[a_k+2k]=..=k$。

接着考虑 $k-1$。不妨令 $t'$ 使得 $\text{M}(E_{t'},a_{k-1})\in (a_k-k,a_k)$。$E_{t'+1}$ 相较于 $E_{t'}$ 少了 $k-1$ 个数，其中小于等于 $\text{M}(E_{t'}, a_{k-1})$ 的有 $k-1$ 个，故第 $a_{k-1}$ 小的数也就往后顺延了 $k-1$ 位。但在往后顺延的过程中必然会遇到空位。不难证明，若 $T[s]=a_k$，则 $s\notin E_{t'}$；若 $T[s]<a_{k-1}$，则 $s\in E_{t'}$。结合 $T[a_k]=T[a_k+k]=..=k$ 可知在往后顺延的过程中必然会跳过一位已经不在 $E_{t'}$ 中的元素，故有 $T[t']=T[t'+(k-1)+1]=T[t'+k]=T[t'+2k]=..=k-1$。同理我们也可以推出 $T[t'']=T[t''+(k-2)+2]=T[t''+k]=..=k-2$，$T[t''']=T[t'''+(k-3)+3]=T[t'''+k]=..=k-3$，故而证明了周期性。

Afterword

这一结论除了可以帮助 $O(n)$ 做出 CF1852A 外，似乎还有很多用途。我已经有了一个毒瘤的点子，可惜现在我困了，不想写了。晚安。