← 返回题目列表

AtCoder · joig2024_d

D. 许多数字

中文机器翻译题面 查看原题

配点: 100 点

問題文

JOI 高校的葵同学,N 行 N 决定在列的每个格子里用十进制表示写整数。具体来说,从上到下 i 行目 (1 \leqq i \leqq N),从左到右 j 列目 (1 \leqq j \leqq N) 的格子里 A_i + B_j 用十进制写。

葵同学想知道她将写多少个数字。也就是说,葵同学写的 N^2 个整数的位数总和想要求出。

A_i (1 \leqq i \leqq N) 和 B_j (1 \leqq j \leqq N) 被给定时,葵要写的 N^2 个整数的位数总和的程序请制作。

制約

  • 1 \leqq N \leqq 150\,000.
  • 1 \leqq A_i \leqq 999\,999\,999 (1 \leqq i \leqq N).
  • 1 \leqq B_j \leqq 999\,999\,999 (1 \leqq j \leqq N).
  • 所有输入值都是整数。

小課題

  1. (5 点) N = 1.
  2. (11 点) N \leqq 2\,000.
  3. (15 点) A_i \leqq 2\,000 (1 \leqq i \leqq N),B_j \leqq 2\,000 (1 \leqq j \leqq N).
  4. (8 点) 100\,000\,000 \leqq A_i \leqq 500\,000\,000 (1 \leqq i \leqq N),100\,000\,000 \leqq B_j \leqq 500\,000\,000 (1 \leqq j \leqq N).
  5. (22 点) 100\,000\,000 \leqq A_i (1 \leqq i \leqq N),100\,000\,000 \leqq B_j (1 \leqq j \leqq N).
  6. (12 点) A_i \leqq 150\,000 (1 \leqq i \leqq N),B_j = j (1 \leqq j \leqq N).
  7. (13 点) B_j = j (1 \leqq j \leqq N).
  8. (14 点)没有额外的限制。

入力

输入按以下格式给出。

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

出力

葵要写的 N^2 个整数 1 行。


入力例 1

3
97 79 7
20 2 21

出力例 1

20

葵在各格子里写的整数如下图所示。

例如,葵从上数第 1 行,从左数第 1 列的格子里写 A_1 + B_1 = 97 + 20 = 117 。另外,从上数写 3 行,从左数第 2 列的格子里写 A_3 + B_2 = 7 + 2 = 9 。

葵要写的 9 个整数是 117, 99, 118, 99, 81, 100, 27, 9, 28 ,各位数是 3, 2, 3, 2, 2, 3, 2, 1, 2 。

。因此,葵要写的 9 个整数的总数是 3 + 2 + 3 + 2 + 2 + 3 + 2 + 1 + 2 = 20 。20 。

因此,这个输入例是小课题。 2, 3, 8 满足约束。


入力例 2

4
8 97 996 9995
1 2 3 4

出力例 2

46

葵在每个格子上写的数字如下图所示。

例如,葵从上数第 2 行,从左数第 3 列的格子里写 A_2 + B_3 = 97 + 3 = 100 写下这个整数,这个整数的总数是 3 。另外,从上到下 4 行,从左数第 2 列的格子里写 A_4 + B_2 = 9\,995 + 2 = 9\,997 写下这个整数,这个整数的总数是 4 。

葵要写的 16 个整数的总数是 46 。46 。

因此,这个输入例是小课题。 2, 6, 7, 8 满足约束。


入力例 3

1
500000000
500000000

出力例 3

10

葵写的整数一共有 1 个,它们的值是 500\,000\,000 + 500\,000\,000 = 1\,000\,000\,000 。这些整数的符号数是 10 。

。因此,葵要写的 1 个整数的总数是 10 。10 。

因此,这个输入例是小课题。 1, 2, 4, 5, 8 满足约束。


入力例 4

7
436981378 523812834 456708479 413571178 506402783 598271009 523936624
401203104 501634329 506090236 527167431 485527116 439442403 568364549

出力例 4

463

因此,这个输入例是小课题。 2, 5, 8 满足约束。