分数: 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