← 返回题目列表

AtCoder · abc353_c

E. 西格玛问题

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

分数: 300 点

问题陈述

对于正整数 x 和 y,定义 f(x, y) 作为剩余部分 (x + y) 除以 10^8.

给你一个正整数序列 A = (A_1, \ldots, A_N) 长度 N。求下列表达式的值:

\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j).


约束

  • 2 \leq N \leq 3\times 10^5
  • 1 \leq A_i < 10^8
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N 
A_1 \ldots A_N

输出

打印答案。


示例输入 1

3
3 50000001 50000002

示例输出 1

100000012
  • f(A_1,A_2)=50000004
  • f(A_1,A_3)=50000005
  • f(A_2,A_3)=3

因此,答案是 f(A_1,A_2) + f(A_1,A_3) + f(A_2,A_3) = 100000012.

请注意,系统不会要求您计算总和除以的余数 10^8.


示例输入 2

5
1 3 99999999 99999994 1000000

示例输出 2

303999988