DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

Magic Contest

返回题目

题解

对于长度为 mmm 的二进制字符串 XXX,考虑如下校验和:

∑i=1miXi(modm+1).\sum_{i=1}^{m} iX_i\pmod{m+1}.i=1∑m​iXi​(modm+1).

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

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

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

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

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

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

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

Solution written by GPT5

m=N+rm=N+r
m=N+r
1,2,4,⋯ ,2r−11,2,4,\cdots,2^{r-1}1,2,4,⋯,2r−1
SSS
NNN
mod
(m+
1)
q<2rq<2^rq<2r
qqq
000
N=1,2N=1,2
N=1,2
NNN
M−N≤18M-N\leq 18M−N≤18
100100100
m(m+1)/2<2.1×1010m(m+1)/2<2.1\times 10^{10}
m(m+1)/2<2.1×1010