Magic Contest

对于长度为 $m$ 的二进制字符串 $X$，考虑如下校验和：

$$\sum_{i=1}^{m} iX_i\pmod{m+1}.$$

校验和为 $0$ 的字符串构成一个能够纠正一次插入或删除的 Varshamov--Tenengolts 码。

当原字符串长度为 $N$ 时，取满足 $2^r\geq N+r+1$ 的最小 $r$，并令 $$。预留位置 作为校验位，再将 的 个比特按顺序放入其余位置。

设数据位产生的校验和为 $a$。取满足 $0\leq q\leq m$ 的整数 $q=(-a)\bmod(m+1)$。由于 ，可以将 的二进制表示放入预留的校验位。这样构造出的字符串校验和为 。

当 $3\leq N\leq 200\,000$ 时，有 $r\leq 18$ 且 $m\leq 2N$。当 $$ 时，将每个比特重复两次。这个短重复码同样可以纠正一次插入。因此，爱丽丝始终满足长度限制，并且对于所有 都有 ，从而获得 分。

鲍勃收到的字符串长度为 $m+1$。枚举每个可能的删除位置 $j$，计算删除该字符后的校验和，并寻找使校验和为 $0$ 的位置。由单次插入纠错码的性质，恢复出的码字是唯一的。利用加权和以及后缀中 1 的数量，可以在总计 $O(m)$ 的时间内计算所有候选校验和。

恢复码字后，按顺序收集位置不是2的幂的字符，即可得到原字符串 $S$。

每次运行的时间复杂度为 $O(\sum N_i)$，辅助空间复杂度为 $O(\max N_i)$。校验和计算中需要的最大整数为 ，在有符号64位整数范围内。

Solution written by GPT5