[ARC136D] Without Carry
题意翻译
给定一个长度为 $n$ 的数列 $S$,设 $A_{i,j}$ 代表 $S_i$ 十进制表示法中从右往左数第 $j$ 位的数,如果字符串长度 $<j$ 则 $A_{i,j} = 0$。
求满足 $\forall k \in [1, 7], A_{i, k} + A_{j, k} < 10$ 的二元数对 $(i, j)$ 的个数。
题目描述
[problemUrl]: https://atcoder.jp/contests/arc136/tasks/arc136_d
長さ $ N $ の整数列 $ A=(A_1,A_2,\cdots,A_N) $ が与えられます.
整数の組 $ (i,j) $ ($ 1\ \leq\ i\ <\ j\ \leq\ N $) であって,$ A_i+A_j $ を筆算で計算する際に繰り上がりが発生しないものの個数を求めてください.
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる.
> $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $
输出格式
答えを出力せよ.
输入输出样例
输入样例 #1
4
4 8 12 90
输出样例 #1
3
输入样例 #2
20
313923 246114 271842 371982 284858 10674 532090 593483 185123 364245 665161 241644 604914 645577 410849 387586 732231 952593 249651 36908
输出样例 #2
6
输入样例 #3
5
1 1 1 1 1
输出样例 #3
10
说明
### 制約
- $ 2\ \leq\ N\ \leq\ 10^6 $
- $ 0\ \leq\ A_i\ \leq\ 10^6-1 $
- 入力される値はすべて整数
### Sample Explanation 1
数えるべき組 $ (i,j) $ は,$ (1,3),(1,4),(2,4) $ の $ 3 $ つです. 例えば,$ A_1+A_3=4+12 $ を計算する際には繰り上がりが発生しないので,$ (i,j)=(1,3) $ は数えます. 反対に,$ A_3+A_4=12+90 $ を計算する際には繰り上がりが発生するので,$ (i,j)=(3,4) $ は数えません.