\(L=6\) とします．

\(0\) 以上 \(10^L\) 未満の整数 \(x,y\) について，以下の条件を満たすことを，\(x\) が \(y\) を dominate している，と呼ぶことにします．

• 各 \(i\) (\(0 \leq i \leq 5\)) について，(\(x\) の \(10^i\) の位の値 ) \(\geq\) (\(y\) の \(10^i\) の位の値 )

\(x+y\) を計算する際に繰り上がりが起きないのは，\((10^L-1-x)\) が \(y\) を dominate しているときです．

よって，各 \(0 \leq s <10^L\) について，\(s\) に dominate される \(A_i\) の個数が分かればよいです．

ここで，問題が \(10\) 進数でなく，\(2\) 進数であった場合を考えると，これは高速ゼータ変換そのものだとわかります．

そして，全く同様のアルゴリズムが \(10\) 進数でも可能です． 具体的には，各 \(i\) (\(0 \leq i \leq 5\)) について，\(x\) の \(10^i\) の位が \(9\) 未満なら \(x+10^i\) に遷移する．というDPを行えばよいです．

計算量は \(O(N+L \times 10^L)\) になります．

解答例(c++)