/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
200 という整数が大好きなりんごさんのために、次の問題を解いてください。
N 個の正整数からなる数列 A が与えられるので、以下の条件をすべて満たす整数の組 (i,j) の個数を求めてください。
- 1 \le i < j \le N
- A_i - A_j は 200 の倍数である。
制約
- 入力は全て整数
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
6 123 223 123 523 200 2000
出力例 1
4
例えば、(i, j) = (1, 3) のとき、A_1 - A_3 = 0 は 200 の倍数です。
(i,j)=(1,3),(1,4),(3,4),(5,6) の 4 つが条件を満たします。
入力例 2
5 1 2 3 4 5
出力例 2
0
条件を満たす組がひとつも無い場合があります。
入力例 3
8 199 100 200 400 300 500 600 200
出力例 3
9
Score : 300 points
Problem Statement
Ringo loves the integer 200. Solve the problem below for him.
Given a sequence A of N positive integers, find the pair of integers (i, j) satisfying all of the following conditions:
- 1 \le i < j \le N;
- A_i - A_j is a multiple of 200.
Constraints
- All values in input are integers.
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
6 123 223 123 523 200 2000
Sample Output 1
4
For example, for (i, j) = (1, 3), A_1 - A_3 = 0 is a multiple of 200.
We have four pairs satisfying the conditions: (i,j)=(1,3),(1,4),(3,4),(5,6).
Sample Input 2
5 1 2 3 4 5
Sample Output 2
0
There may be no pair satisfying the conditions.
Sample Input 3
8 199 100 200 400 300 500 600 200
Sample Output 3
9