[R25C]有序对 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个包含 $n$ 个整数的序列 $A = (A_1, A_2, ..., A_n)$。和一个整数 $m$。

请计算满足以下所有条件的有序对 $(i, j)$ 的数量：

1. $1 \leq i < j \leq n$
2. $A_i = A_j$
3. $i \bmod m = j \bmod m$（两个位置的下标对 $m$ 取模后的余数相同）

格式

输入格式

第一行包含两个由空格分隔的整数 $n$ 和 $m$。

第二行包含 $n$ 个由空格分隔的整数 $A_{1}, A_{2}, \ldots, A_{n}$ ，代表序列 $A$。

输出格式

输出一个整数，表示满足条件的有序对的数量。

样例

样例输入 #1

5 2
1 2 3 2 1

样例输出 #1

2

样例解释 #1

$(1,5)$，$(2,4)$ 符合条件。

数据规模

对于 $40\%$ 的数据，$1 \leq m < n \leq 10^3$。

对于 $100\%$ 的数据，$1 \leq m < n \leq 10^6$，$1 \leq A_i \leq 10^6$。