← 返回题目列表

Codeforces · 2095/E

E. 配对计数

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

你被给予 素数 数字 $$$p$$$、$$$n$$$ 整数 $$$a_1、a_2、\ldots、a_n$$$ 和整数 $$$k$$$。

求 $$$(a_i \oplus a_j)(a_i^2 \oplus a_j^2) \equiv k \bmod p$$$ 的索引对 $$$(i, j)$$$ ($$$1 \le i \lt j \le n$$$) 的数量。

这里$$$\oplus$$$表示按位异或运算。

输入

第一行包含整数 $$$n, p, k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$2 \le p \le 10^9$$$, $$$0 \le k \le p-1$$$)。 $$$p$$$ 保证是素数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le p-1$$$)。保证所有元素都不同。

输出

输出一个整数——问题的答案。

示例

输入
复制

3 3 2
0 1 2

输出
复制

1

输入
复制

6 11 2
1 3 5 6 7 8

输出
复制

3

注意

在第一个示例中:

$$$(0\oplus1)(0^2 \oplus 1^2) = 1 \equiv 1 \bmod 3$$$。

$$$(0\oplus2)(0^2 \oplus 2^2) = 8 \equiv 2 \bmod 3$$$。

$$$(1\oplus2)(1^2 \oplus 2^2) = 15 \equiv 0 \bmod 3$$$。

因此只有 $$$1$$$ 对满足条件。

在第二个示例中,有 $$$3$$$ 这样的对:$$$(1, 5)$$$、$$$(1, 6)$$$、$$$(3, 6)$$$。