如何枚举所有竖式乘法？

难道不是算出总数比枚举所有情况更困难吗 ()

先枚举乘数的位数 $k=1,\cdots,d$。注意到中间过程的每个数是独立的，且只有 $0,d,d+1$ 三种情况，因此可以枚举，共 $3^k-1$ 种情况。枚举的复杂度是 $\sum_{k=1}^d(3^k-1)=O(3^d)$。

算最后结果的位数时，直接算可能的最小和最大位数，用极端情况贪心地给被乘数、乘数的每一位、或者过程的每一个结果赋值，然后模拟竖式运算的过程即可。

• 最大情况显然令被乘数为 $\underbrace{99\cdots9}_{\text{$d$ 个 $9$}}$，如果该位中间过程为 $d$ 位则该位乘数为 $1$，如果该位中间过程为 $d+1$ 位则该位乘数为 $9$。
• 最小情况（$0$ 只有一种对应的乘数，不计）：
  • 如果只有 $d$，则所有非零过程得到的都是 $10^{d-1}$。
  • 如果只有 $d+1$，则所有非零过程得到的都是 $10^d$。
  • 如果同时有 $d$ 和 $d+1$，则令被乘数为 $2\cdot10^{d-1}$，乘数为 $1$ 或 $5$，可以发现这样一定不会产生进位。

总复杂度 $O(d\cdot3^d)$。