题解

思路

不妨令 $A_1\le A_2$。

做法

两数之和的位数只能是 $A_2$ 或 $A_2+1$，其他 $A_3$ 的答案为零。先计算和仍为 $A_2$ 位的有序对数 $L$：若 $A_1=A_2$，令 $p=10^{A_1-1}$，则 $L=4p(8p+1)$；若 $A_1<A_2$，则 $L=9\cdot10^{A_1-1}\left(9\cdot10^{A_2-1}-(11\cdot10^{A_1-1}-1)/2\right)$。这些式子来自固定 $X_1$ 后，合法 $X_2$ 构成的连续区间求和。所有 $(X_1,X_2)$ 共 $81\cdot10^{A_1+A_2-2}$ 对，所以 $A_3=A_2$ 时答案为 $L$，$A_3=A_2+1$ 时答案为总数减 $L$。

复杂度

用快速幂在模意义下计算十的幂，并用 $2$ 的逆元处理除法，单组时间复杂度为 $O(\log(A_1+A_2))$，空间复杂度为 $O(1)$。