# 基因突变：题解

## 解法比较

出题人解法按数位处理两种解释之差。对严格小于上界的前缀，只保存差值绝对值较小的状态；差值足够为正时，剩余位不能改变比较结果，可把全部后缀一次计入；足够为负时舍弃。与上界相同的前缀另行维护。下文关于差值递推及不可逆阈值的证明，也解释了这一状态压缩。

Codex（GPT-6）的实现把是否紧贴上界纳入统一状态，并使用可证明的正负饱和值。设位数为 $L$ 、进制参数为 $n$ ，有界差值 DP 的时间上界为 $O(Ln^2)$ ，含输入的空间为 $O(L+n)$ .

## 同时维护两种比较

令 $L=\max(L_A,L_B)$ ，在较短数字前补零，按从高位到低位处理。用紧贴上界标记 $t$ 表示已选择的前缀是否仍等于 $B$ 的前缀。另维护已处理前缀的能力差 $d=F(x_{\mathrm{prefix}})-F(A_{\mathrm{prefix}})$ .

当前标准数码为 $a_i$ ，选择数码 $c$ 后，能力差变为

$$d'=md+c-a_i$$

若 $t$ 为真，允许 $0\le c\le b_i$ ；否则允许 $0\le c<n$ .新的上界标记为 $t\land(c=b_i)$ .

## 有界差值状态

令 $T=n-1$ .当 $d\ge T$ 时，因为 $m\ge2$ 且 $c-a_i\ge-T$ ，下一步仍有 $d'\ge2T-T=T$ .因此能力差以后始终为正，只需记成 $T$ .同理，$d\le-T$ 后始终为负，只需记成 $-T$ .

于是每步把 $d'$ 截断到 $[-T,T]$ .中间的差值保留精确值，两个端点代表已经确定的正、负差；无需存储整个大整数。

定义 $\mathrm{dp}[d][t]$ 为当前前缀状态的方案数。初始为 $\mathrm{dp}[0][1]=1$ ，按上述转移滚动计算，所有计数对模数取模。处理完全部位后，将 $d>0$ 的状态相加。

## 正确性

上界标记枚举且仅枚举不超过 $B$ 的固定长度数码串，前导补零使每个候选整数对应唯一串。能力差递推等于位置权值公式；截断状态的符号不可能再改变，所以不会改变最终的严格大小比较。归纳可知 DP 精确统计每个状态，最后的正差状态就是全部合法答案。

## 复杂度

共有 $O(n)$ 个差值状态，每步枚举至多 $n$ 个数码。时间复杂度为 $O(Ln^2)$ ；保存输入和两层状态的空间为 $O(L+n)$ .