B. 大数加法 – 详细题解

问题重述

给定一个整数 $x$（$10 \le x \le 10^{18}$），判断是否存在两个位数相同的大整数 $A$ 和 $B$，使得 $A + B = x$。
大整数定义为：其每一位数字都在 $5$ 到 $9$ 之间（包含端点）。

关键观察

设 $A$ 和 $B$ 的位数为 $L$。那么它们每一位上的数字 $a_i, b_i \in [5,9]$，且 $A$ 和 $B$ 的长度相同。
两个 $L$ 位数相加，和可能是一位 $L$ 位数，也可能是 $L+1$ 位数（当最高位的和加上进位达到 $10$ 或以上时）。
因此可能的位数情况有两种：

1. 和 $x$ 恰好有 $L$ 位（即没有额外的进位溢出）；
2. 和 $x$ 有 $L+1$ 位（最高位只能为 $1$，因为两个最多 $9$ 的数字相加再加进位最多 $19$）。

所以对于给定的 $x$，我们只需检查两种可能的位数：$L = \text{len}(x)$ 和 $L = \text{len}(x)-1$（当 $\text{len}(x) \ge 2$ 时）。
如果其中一种情况可行，则答案为 YES，否则为 NO。

数位处理与进位约束

从低位到高位逐位判断是否存在合法的 $a_i, b_i$ 以及进位值。
设 $d_i$ 为 $x$ 从低位开始第 $i$ 位上的数字（$i=0$ 表示个位）。
设进位数 $c_i$ 表示第 $i$ 位相加后产生的进位（$c_i \in \{0,1\}$），其中 $c_0 = 0$（最低位无进位输入）。
对于第 $i$ 位（$i=0 \dots L-1$），我们有：

[ a_i + b_i + c_i = d_i + 10 \cdot c_{i+1} ]

其中 $c_{i+1}$ 表示向高位的进位（$0$ 或 $1$）。
已知 $a_i, b_i \in [5,9]$，因此 $a_i + b_i \in [10, 18]$。

等式分析

给定 $c_i$ 和 $d_i$，我们需要判断是否存在 $c_{i+1} \in \{0,1\}$ 以及 $a_i,b_i \in [5,9]$ 使得上式成立。
因为 $a_i + b_i = d_i + 10 c_{i+1} - c_i$。

• 当 $c_{i+1}=0$ 时，$a_i + b_i = d_i - c_i$，必须 $\ge 10$ 且 $\le 18$。
• 当 $c_{i+1}=1$ 时，$a_i + b_i = d_i + 10 - c_i$，也必须 $\ge 10$ 且 $\le 18$。

同时注意 $d_i - c_i$ 和 $d_i+10-c_i$ 均为正整数（因为 $d_i \ge 0$，且最低位 $d_0$ 来自 $x$ 的个位，可能为 $0$，但需保证最终和为正整数）。

更简单的判定方式是：
对于给定的 $c_i$ 和 $d_i$，可能的进位输出 $c_{i+1}$ 必须满足：

[ 10 \le d_i + 10c_{i+1} - c_i \le 18 ]

即差值落在 $[10,18]$。
若存在 $c_{i+1} \in \{0,1\}$ 满足该不等式，则这一位可行，并可将 $c_{i+1}$ 作为下一位置的进位输入。

因此我们可以从最低位开始，维护当前可能的进位值集合 $\{0,1\}$ 中哪些是可行的，然后逐位转移。
最终处理完所有 $L$ 位后，需检查最终的进位 $c_L$ 是否满足长度要求：

• 如果 $x$ 的位数等于 $L$（即没有最高进位），则必须有 $c_L = 0$；
• 如果 $x$ 的位数等于 $L+1$（存在额外进位），则必须有 $c_L = 1$，并且此时 $x$ 的最高位必须为 $1$（因为两个 $L$ 位数相加，最高位产生进位 $1$，且不会超过 $1$）。

算法步骤

对于给定的 $x$：

1. 提取其十进制数字串 $s$（高位到低位）。
2. 分别尝试两种长度情况：
   • 情况 A：$L = |s|$，要求最终进位 $c_L = 0$。
   • 情况 B：$L = |s|-1$（当 $|s| \ge 2$ 时），要求最终进位 $c_L = 1$，并且 $s$ 的最高位必须为 $1$（因为进位得到的最高位只能是 $1$）。
3. 对于每种情况，进行从低位到高位的进位状态模拟：
   • 初始进位集合 $\text{carry} = \{0\}$。
   • 对于第 $i$ 位（$i=0,\dots,L-1$），取 $x$ 的对应位数字 $d_i$（低位对齐，不足的高位补 $0$ 或直接忽略）。
   • 对于当前 $\text{carry}$ 中的每个值 $c_i$，检查是否可以为 $c_{i+1}=0$ 或 $1$，使得 $10 \le d_i + 10c_{i+1} - c_i \le 18$。将可行的 $c_{i+1}$ 加入新的集合。
   • 若某一步集合为空，则该情况不可行。
4. 若任一情况成功，输出 YES，否则 NO。

时间复杂度

每个测试用例处理 $O(|s|)$ 位，$|s| \le 18$，且常数极小，可在 $1$ 秒内轻松处理 $t \le 10^4$ 个测试用例。

正确性说明

该算法本质上是确定性有限自动机 （进位作为状态）的可行性判定。由于每位只有 $0$ 或 $1$ 两种进位输入，且转移规则完全由 $d_i$ 决定，因此通过逐位检查即可确定是否存在满足条件的 $A,B$。

注意：我们不需要显式求出 $A,B$，只需存在性。同时，由于 $a_i,b_i$ 的范围连续且转移条件简单，没有必要枚举具体数值，只需验证进位转移的可能性。

示例验证

• $x=1337$：位数 $4$，尝试 $L=4$。低位到高位模拟可行，最终进位为 $0$，成功（如 $658+679$）。
• $x=200$：位数 $3$，尝试 $L=3$：最低位 $d_0=0,c_0=0$，只能取 $c_1=1$（因为 $0+10-0=10$ 在 $[10,18]$）。继续模拟至高位，发现无法满足，再尝试 $L=2$（即看作 $+00$? 实际 $L=2$ 时，$x$ 应有 $3$ 位，所以最高位是进位得到的 $1$，但 $200$ 的最高位是 $2$，矛盾），所以无解。
• $x=69$：位数 $2$。尝试 $L=2$：个位 $9$，$c_0=0$，$9+10c_1 \in [10,18]$ 得 $c_1=1$。十位 $6$，$c_1=1$，需 $6+10c_2-1 \in[10,18]$，若 $c_2=0$ 得 $5<10$；若 $c_2=1$ 得 $15$ 可行，但最终进位 $c_2=1$ 要求 $L=2$ 时最高位由进位产生，但 $x$ 的十位是 $6$ 不是 $1$，矛盾。所以 $NO$。

结论

本题通过分析进位规律，使用简单的数位 DP（状态数仅为 $2$）即可高效求解，无需复杂的高精度运算。代码实现时注意字符串的索引转换和边界情况即可。