#P9430. 二元数对

    ID: 5768 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF1900普及+/提高-计数 DP贡献法重复元素除重多维前缀和

二元数对

题面翻译

给定一个长度为 nn 的数列 SS,设 Ai,jA_{i,j} 代表 SiS_i 十进制表示法中从右往左数第 jj 位的数,如果字符串长度 <j<j 则 Ai,j=0A_{i,j} = 0。

求满足 ∀k∈[1,7],Ai,k+Aj,k<10\forall k \in [1, 7], A_{i, k} + A_{j, k} < 10 的二元数对 (i,j)(i, j) 的个数。

输出格式

答えを出力せよ.

样例 #1

样例输入 #1

4
4 8 12 90

样例输出 #1

3

样例 #2

样例输入 #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

样例输入 #3

5
1 1 1 1 1

样例输出 #3

10

提示

制約

  • 2 ≤ N ≤ 106 2\ \leq\ N\ \leq\ 10^6
  • 0 ≤ Ai ≤ 106−1 0\ \leq\ A_i\ \leq\ 10^6-1