问题重述

给定一个质数 $p$，一个长度为 $n$ 的数组 $a$（元素互异，且 $0 \le a_i < p$），以及一个整数 $k$ ($0 \le k < p$)。
定义运算 $\oplus$，表面上是“按位异或”，但实际上链接中的小游戏揭示 $\oplus$ 表示乘法。
求满足下式的下标对 $(i, j)$ 的数量（$1 \le i < j \le n$）：

$$(a_i \oplus a_j) \cdot (a_i^2 \oplus a_j^2) \equiv k \pmod p $$

题意转化：$\oplus$ 的真实含义

题目中 [bitwise XOR operation] 的链接指向一个 Wordle 游戏。解出单词为 MULTIPLY（乘法）。
因此实际运算为：

• $a_i \oplus a_j = a_i \times a_j \pmod p$
• $a_i^2 \oplus a_j^2 = a_i^2 \times a_j^2 \pmod p$

代入原式：

$$(a_i \times a_j) \cdot (a_i^2 \times a_j^2) \equiv k \pmod p $$$$a_i^3 \cdot a_j^3 \equiv k \pmod p$$

结论：问题转化为求

$$a_i^3 \cdot a_j^3 \equiv k \pmod p$$

且 $i < j$ 的配对数量。

算法推导

固定 $j$，我们需要快速统计在 $j$ 之前有多少个 $i$ 满足：

$$a_i^3 \equiv k \cdot (a_j^3)^{-1} \pmod p$$

由于 $p$ 是质数，利用费马小定理可以求逆元：
对于任意非零元 $x$，有 $x^{-1} \equiv x^{p-2} \pmod p$（前提 $x \not\equiv 0$）。

我们可以从左到右遍历数组，维护一个哈希表 mp，键为 $a_i^3 \bmod p$，值为其出现次数。
对于当前元素 $a_j$：

1. 计算 $x = a_j^3 \pmod p$。
2. 如果 $x \neq 0$，计算 $inv = x^{-1} \pmod p$，则与 $a_j$ 配对的 $a_i$ 需要满足 $a_i^3 \equiv k \cdot inv \pmod p$。
3. 在答案中累加 mp[k * inv % p]。
4. 更新 mp[x]++。

注意几个特殊情况：

• $k = 0$：条件变为 $a_i^3 \cdot a_j^3 \equiv 0 \pmod p$。由于 $p$ 是质数，无零因子，即至少一个 $a_i^3 \equiv 0 \pmod p$，即 $a_i = 0$。
  题目保证所有元素互异，因此数组中至多一个 $0$。
  如果存在 $0$，则它与任何其他元素配对均满足 $0 \cdot a_j^3 = 0$，故答案为 $n-1$；否则为 $0$。
• $a_j = 0$ 且 $k \neq 0$：方程变为 $0 \equiv k \pmod p$，不成立。因此 $a_j = 0$ 不可能与任何 $i$ 配对（因为 $k \neq 0$）。代码中直接 continue 跳过。

标准程序详解

#include <bits/stdc++.h>
using namespace std;

#define ll long long

int a[300005];

// 快速幂：计算 x^n mod p
ll power(ll x, int n, int p) {
    x %= p;
    ll res = 1;
    while (n) {
        if (n & 1) res = (res * x) % p;
        x = (x * x) % p;
        n >>= 1;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, p, k;
    cin >> n >> p >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    // 特判 k=0
    if (k == 0) {
        // 只有数组中存在0时，0与其他任意元素配对成立，答案为 n-1
        cout << (*min_element(a + 1, a + n + 1) == 0 ? n - 1 : 0) << '\n';
        return 0;
    }

    map<int, int> mp;
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] == 0) continue;   // k != 0 时，0无法满足方程

        int x = power(a[i], 3, p);          // a_i^3 mod p
        int inv = power(x, p - 2, p);       // 费马小定理求逆元
        ans += mp[(k * (ll)inv) % p];       // 统计前面满足 a_j^3 ≡ k * inv 的元素数
        ++mp[x];                            // 将当前 a_i^3 加入哈希表
    }
    cout << ans << '\n';
    return 0;
}