2025 杭电多校 9

2025“钉耙编程”中国大学生算法设计暑期联赛（9）

1009

求解：
$S_p = \bigoplus_{i=1}^{p-1} (\text{inv}(i) + 2^k)(i + 4^k)$
其中 $k = \lceil p/119 \rceil$。

我们知道，a + b = (a ⊕ b) + 2 * (a & b)。加法比异或多了一个“进位”项。

当参与相加的数在二进制表示上完全不重叠时，加法不产生进位，此时 a + b = a ⊕ b。

表达式展开：
$T_i = (\text{inv}(i) + 2^k)(i + 4^k) = (i \cdot \text{inv}(i)) + (i \cdot 2^k) + (\text{inv}(i) \cdot 2^{2k}) + 2^{3k}$
将这四项视为四个独立的数 A, B, C, D。

• $A = i \cdot \text{inv}(i)$: 由于 $1 \le i, \text{inv}(i) < p$，我们有 $A < p^2$。这部分占据了二进制的低位。
• $B = i \cdot 2^k$: 相当于将 i 的二进制表示左移 k 位。
• $C = \text{inv}(i) \cdot 2^{2k}$: 相当于将 inv(i) 左移 2k 位。
• $D = 2^{3k}$: 只有一个比特位为1。

不重叠的关键条件在于：A 的最高位，不能与 B 的最低位（第 k 位）重叠。

这需要 A 所占用的位数小于 k，即 $A < 2^k$。由于 $A < p^2$，我们只需要满足 $p^2 < 2^k$ 即可。

根据题设 $p \approx 119k$，我们的条件 $p^2 < 2^k$ 就变成了 $(119k)^2 < 2^k$。这是一个关于 k 的指数不等式。通过简单的计算或二分查找，我们可以发现：

• 当 k = 22 时, $(119 \cdot 22)^2 \approx 6.85 \times 10^6 > 2^{22} \approx 4.19 \times 10^6$。不满足。
• 当 k = 23 时, $(119 \cdot 23)^2 \approx 7.49 \times 10^6 < 2^{23} \approx 8.38 \times 10^6$。满足。

因此

• 当 k >= 23 时，可以尝试优化。
• 当 k < 23 时，p 相对较小，暴力计算即可。

因此当 k >= 23 时，我们可以将原式改写并利用异或的结合律重排：
$S_p = \bigoplus_{i=1}^{p-1} T_i = \bigoplus_{i=1}^{p-1} (A \oplus B \oplus C \oplus D)$
$S_p = \left(\bigoplus_{i=1}^{p-1} A_i\right) \oplus \left(\bigoplus_{i=1}^{p-1} B_i\right) \oplus \left(\bigoplus_{i=1}^{p-1} C_i\right) \oplus \left(\bigoplus_{i=1}^{p-1} D_i\right)$

现在我们逐一简化这四部分：

1. Part D: $\bigoplus_{i=1}^{p-1} 2^{3k}$。一个固定的数异或了 p-1 次（偶数次），结果为 0。
2. Part B & C: $(\bigoplus i \cdot 2^k) \oplus (\bigoplus \text{inv}(i) \cdot 2^{2k})$。
   • 可以提取出来：$(\bigoplus i) \cdot 2^k \oplus (\bigoplus \text{inv}(i)) \cdot 2^{2k}$。
   • 当 i 遍历 1 到 p-1 时，inv(i) 只是 {1, ..., p-1} 的一个排列，所以 $\bigoplus i = \bigoplus \text{inv}(i)$。令此值为 $S_{xor}$。
   • 此部分化为 $(S_{xor} \cdot 2^k) \oplus (S_{xor} \cdot 2^{2k})$。
3. Part A: $\bigoplus_{i=1}^{p-1} (i \cdot \text{inv}(i))$。
   • 这里的乘积是整数乘积，而非模 p 意义下的。
   • 利用数论中的配对思想：除了 i=1 和 i=p-1，其他的 i 和 inv(i) 总是成对出现且不相等。
   • 对于一对 (j, k) 其中 k=inv(j)，它们在异或和中贡献的项是 (j*k) 和 (k*j)，这两项完全相同，异或后为0。
   • 因此，这部分的和只剩下 i=1 和 i=p-1 的项：$(1 \cdot \text{inv}(1)) \oplus ((p-1) \cdot \text{inv}(p-1)) = 1 \oplus (p-1)^2$。
   • 因为 $(p-1)^2$ 是偶数，这等价于 $(p-1)^2+1 = p^2 - 2p + 2 = p(p - 2) + 2$。

最终公式
将三部分合并，由于它们二进制不重叠，异或等价于加法：
$S_p = \left( p(p - 2) + 2 \right) + \left( S_{xor} \cdot 2^k \right) + \left( S_{xor} \cdot 2^{2k} \right)$

#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using namespace std;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while (48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for (auto x : a) cout << x << " "; cout << "\n";
template <class T1, class T2> ostream &operator<<(ostream &os, const std::pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; i++) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; i++) cerr << *i << " "; cerr << '\n'; }
using pii = pair<int, int>;
const int inf = 1e18;
const int MOD = 998244383;

ostream &operator<<(ostream &os, i128 n) {
    if (n == 0) return os << 0;
    string s; while (n > 0) s += char('0' + n % 10), n /= 10;
    reverse(s.begin(), s.end());
    return os << s;
}

template <class T>
constexpr T power(T a, i64 b) { T res {1}; for (; b; b /= 2, a *= a) if (b % 2) res *= a; return res; }
constexpr i64 mul(i64 a, i64 b, i64 p) { i64 res = a * b - (i64)(1.L * a * b / p) * p; res %= p; if (res < 0) res += p; return res; }
template <i64 P>
struct MInt {
    i64 x;
    constexpr MInt() : x {0} {}
    constexpr MInt(i64 x) : x {norm(x % getMod())} {}
    static i64 Mod;
    constexpr static i64 getMod() { return P > 0 ? P : Mod; }
    constexpr static void setMod(i64 Mod_) { Mod = Mod_; }
    constexpr i64 norm(i64 x) const { if (x < 0) x += getMod(); if (x >= getMod()) x -= getMod(); return x; }
    constexpr i64 val() const { return x; }
    constexpr MInt operator-() const { MInt res; res.x = norm(getMod() - x); return res; }
    constexpr MInt inv() const { return power(*this, getMod() - 2); }
    constexpr MInt &operator*=(MInt rhs) & { if (getMod() < (1ULL << 31)) x = x * rhs.x % int(getMod()); else x = mul(x, rhs.x, getMod()); return *this; }
    constexpr MInt &operator+=(MInt rhs) & { x = norm(x + rhs.x); return *this; }
    constexpr MInt &operator-=(MInt rhs) & { x = norm(x - rhs.x); return *this; }
    constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) { MInt res = lhs; res *= rhs; return res; }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) { MInt res = lhs; res += rhs; return res; }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) { MInt res = lhs; res -= rhs; return res; }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) { MInt res = lhs; res /= rhs; return res; }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) { i64 v; is >> v; a = MInt(v); return is; }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) { return os << a.val(); }
    friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
    friend constexpr bool operator<(MInt lhs, MInt rhs) { return lhs.val() < rhs.val(); }
};
template <>
i64 MInt<0>::Mod = 998244353;
constexpr int P = 998244353;
using Z = MInt<P>;
using DZ = MInt<0>;

void solve() {
    int p = read();
    int k = (p + 118) / 119;
    Z ans = 0;

    if (k >= 23) {
        int res = 0;
        Z t = power(Z(2), k);
        for (int i = (p - 1) / 4 * 4; i <= p - 1; i++) {
            res ^= i;
        }
        ans = Z(res) * (t * t + t);
        ans += Z(p) * Z(p - 2) + 2;
    } else {
        DZ::setMod(p);
        i128 res = 0;
        i128 t = 1ll << k;
        for (int i = 1; i < p; i++) {
            res ^= (DZ(i).inv().val() + t) * (i + t * t);
        }
        ans = res;
    }

    cout << ans << '\n';
}

signed main() {
    for (int T = read(); T--; solve());
    // solve();
    return 0;
}