2026 年北京预赛

提示

先独立尝试，再展开工具说明与想法来源。

想想一道相关的题

先回想这道题的想法，再试试当前题。

思路

有限状态方法在这里就是逐位加法记进位，不需要自动机理论。状态是可达进位的集合，而非任选一条进位路径。

想法从哪来：先把“任意拆分至少含一个1”取反，变成能否由两个无数码1的数相加。枚举完整的大整数不可行，但十进制加法在相邻两位间只传递一个进位，所以先试列出输入进位 $0, 1$ 的逐位表。从个位往上读，只需跟踪哪些进位仍然可达；一旦两种都可达，后续就不会再失败。由此先得到非负加数的不可表示数形，再补查原题要求两个正加数带来的例外。最后才做模11求和，利用 $10 \equiv - 1$ 将数位权重化成正负交替。不能把允许零加数的状态表直接当作原问题答案。

条件等价于 $n$ 不能写成两个不含数码 $1$ 的正整数之和。逐位相加时只需记录进位 $0$ 或 $1$ ，可用两状态表完整刻画不可表示的十进制串；随后利用 $10 \equiv - 1 (mod 11)$ 求和。

解答

记

D = {0, 2, 3, 4, 5, 6, 7, 8, 9} .

先允许两个加数为非负整数，并从个位向高位相加。若当前输入进位为 $c \in {0, 1}$ ，目标数字为 $d$ ，输出进位为 $c^{'}$ ，则需要找 $u, v \in D$ 使 $u + v + c = d + 10 c^{'}$ 。直接检查可得所有可能的 $c^{'}$ ：

d 012 3, 4, 5, 6, 7, 8 9 c = 0 {0, 1} {1} {0, 1} {0, 1} {0} c = 1 {1} {0, 1} {1} {0, 1} {0, 1}

初始进位为 $0$ ，最高位处理完后必须仍能取 $0$ 。一旦可达进位集合变成 ${0, 1}$ ，以后永远保持为 ${0, 1}$ 。在它仍为 ${0}$ 时，读到数字 $9$ 仍为 ${0}$ ，读到数字 $1$ 变为 ${1}$ ；在状态 ${1}$ 时，只有数字 $0$ 或 $2$ 能使它继续保持 ${1}$ 。因此，不能写成两个不含数码 $1$ 的非负整数之和的数，恰为十进制形状

每位为 0 或 2 ε \dots ε 1 t 位 99 \dots 9, (1)

其中允许最高处补零，也允许 $t = 0$ 。

还需排除某个加数为 $0$ 的情形。若一个正整数本身不含数码 $1$ ，设它最低非零位为 $d \cdot 1 0^{j}$ ，其中 $d \in {2, 3, \dots, 9}$ 。若 $d = 2$ 且还有更高非零部分，可拆成 $2 \cdot 1 0^{j}$ 与其余部分；若 $d \geq 4$ ，可拆成 $2 \cdot 1 0^{j}$ 与原数减去它。若 $d = 3$ 且有更高部分，可按该位与更高部分拆开；若原数恰为 $3 \cdot 1 0^{j}$ 且 $j \geq 1$ ，则

3 \cdot 1 0^{j} = 2 + (3 \cdot 1 0^{j} - 2),

而右边第二项的十进制数字为一个 $2$ 、若干个 $9$ 和末位 $8$ ，仍不含 $1$ 。故不能拆成两个正的无数码 $1$ 整数的额外情形只有

3, 2 \cdot 1 0^{j} (j \geq 0) . (2)

于是专一数恰由 (1)、(2) 两类组成。

现在令 $N = 2026$ ，把所有小于 $1 0^{N}$ 的数写成恰好 $N$ 位，允许前导零。在 (1) 中固定末尾 $9$ 的个数 $t$ ，则数字 $1$ 的位置为 $1 0^{t}$ ，其上有 $h = N - t - 1$ 个可独立取 $0$ 或 $2$ 的数位。固定 $t$ 的这些数之和为

2^{h} (2 \cdot 1 0^{t} - 1 + k = t + 1 \sum N - 1 1 0^{k}) .

模 $11$ 时 $10 \equiv - 1$ 。因为 $N$ 为偶数，括号内在 $t$ 为偶数时同余于 $0$ ，在 $t$ 为奇数时同余于 $- 3$ 。令 $N = 2 m$ ，便有

形如 (1) 的数 \sum n \equiv - 3 j = 0 \sum m - 1 4^{j} = 1 - 4^{m} (mod 11) .

这里 $m = 1013 \equiv 3 (mod 5)$ ，而 $4^{5} \equiv 1 (mod 11)$ ，故

1 - 4^{1013} \equiv 1 - 4^{3} \equiv 1 - 9 \equiv 3 (mod 11) .

额外一类 (2) 在范围内的总和为

3 + 2 j = 0 \sum N - 1 1 0^{j} \equiv 3 (mod 11),

因为 $N$ 为偶数， $\sum_{j = 0}^{N - 1} (- 1)^{j} = 0$ 。最终

S \equiv 6 (mod 11) .

复核

状态表同时包含“产生进位”和“不产生进位”的所有可能，起始与结束进位均已限定为零。由非负加数过渡到正加数时，单独检查了零加数造成的全部例外；两类专一数互不重叠。固定 $N$ 位并允许前导零不会重复计数，因为形状 (1) 中唯一的数码 $1$ 决定了 $t$ 。

方法总结

十进制加法的禁位问题可建成有限状态机：状态只记录进位，转移由允许数字的和集决定。先完成语言分类，再利用模数下底数的短周期对整类数求和，能把极大的位数降为有限计算。

作答

解析

提示

想想一道相关的题

思路

解答

复核

方法总结