基因突变：题解¶

解法比较¶

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

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)\) .