Let \(L=6\).

For integers \(x,y\) between \(0\) and \(10^L-1\), let us say \(x\) dominates \(y\) when the following condition is satisfied.

• For each \(i\) (\(0 \leq i \leq 5\)), (the digit in the \(10^i\)’s place of \(x\)) \(\geq\) (the digit in the \(10^i\)’s place of \(y\))

Calculation of \(x+y\) involves no carrying when \((10^L-1-x)\) dominates \(y\).

Thus, the problem can be solved if, for each \(0 \leq s <10^L\), the number of \(A_i\) dominated by \(s\) is known.

Here, if the problem is in base \(2\) instead of base \(10\), we can see that this is the fast zeta transform itself.

Additionally, the same algorithm is feasible in base \(10\). Specifically, we should do DP with a transition from \(x\) to \(x+10^i\) if the digit in the \(10^i\)’s place of \(x\) is less than \(9\), for each \(i\) (\(0 \leq i \leq 5\)).

Our solution runs in \(O(N+L \times 10^L)\) time.

Sample submission (c++)