题解：P17226 [Math×Girl²] 终末电台
小粉兔
·
·
题解
::::info[注意]{open}
本文撰写时使用了 DeepSeek V4 Flash 20260731 进行辅助。
::::
1. 问题转化
把档位看作 \mathbb F_p 上的加法群。每次的改变量必须是模 p 的非零二次剩余，因此合法改变量集合是
R = \{ x \in \mathbb F_p^{\times} \mid \chi(x) = +1 \} \text{，}
其中 \chi(x) = \bigl( \frac{x}{p} \bigr) 为 Legendre 符号，并约定 \chi(0) = 0。
答案就是方程
x_1 + x_2 + \cdots + x_k = n \text{，} \qquad x_1, \ldots, x_k \in R
的有序解组数，记作 a_k(n)。令 b_+ 为 R 的指示函数，则 a_k 就是 b_+ 在循环群 \mathbb F_p 上的 k 重卷积：
a_k = b_+^{* k} \text{。}
2. 循环卷积与 DFT / IDFT
设 \omega = \mathrm{e}^{2 \pi \mathrm{i} / p} = \cos(2 \pi / p) + \mathrm{i} \sin(2 \pi / p) 为第一象限中的首个 p 次本原单位根。对函数 f \colon \mathbb F_p \to \mathbb C，熟知离散 Fourier 变换及其逆
\operatorname{DFT}(f)(r) = \sum_{x \in \mathbb F_p} f(x) \, \omega^{r x} \text{，} \qquad \operatorname{IDFT}(f)(r) = \sum_{x \in \mathbb F_p} f(x) \, \omega^{-r x} \text{。}
循环卷积定义为
(f * g)(n) = \sum_{x + y = n} f(x) g(y) \text{。}
熟知有 \operatorname{DFT}(\operatorname{IDFT}(f)) = \operatorname{IDFT}(\operatorname{DFT}(f)) = p \, f 以及卷积定理：
f * g = \frac{1}{p} \operatorname{IDFT}(\operatorname{DFT}(f) \cdot \operatorname{DFT}(g)) \text{。}
因此
a_k = \frac{1}{p} \operatorname{IDFT}(\operatorname{DFT}(b_+)^{\odot k}) \text{，}
其中 \odot k 表示逐点 k 次幂。
3. 答案函数只依赖三类位置
观察 a_k(n) 在二次剩余乘法下的不变性。若 u \in R，在求和
a_k(n) = \sum_{x_1 + \cdots + x_k = n} b_+(x_1) \cdots b_+(x_k)
中作变量替换 x_i \mapsto u x_i。由于 u R = R，有 b_+(u x_i) = b_+(x_i)，而新的和为 u n，所以
a_k(n) = a_k(u n) \text{。}
因此对任意 n \ne 0，a_k(n) 只取决于 \chi(n)。于是引入三个互不相交的指示数组
b_0(x) = [x = 0] \text{，} \qquad b_+(x) = [\chi(x) = +1] \text{，} \qquad b_-(x) = [\chi(x) = -1] \text{，}
则 a_k 一定能写成它们的线性组合。记全 1 数组为 \mathbf{1}，则
\mathbf{1} = b_0 + b_+ + b_- \text{。}
目标变为找到线性组合的系数与 p 和 k 的关系。
::::info[注意]{open}
上述结论也可以通过观察 p, k 较小的情况猜测得到。
::::
4. 复数上的 Gauß 和
下面只在推导时使用复数 \omega 与 Gauß 和
G = \sum_{x \in \mathbb F_p} \omega^{x^2} \text{，}
也等价地定义为 G = \sum_{x} \bigl( \frac{x}{p} \bigr) \omega^{x}，不过这里我们采取第一种定义。
用到的两个结论是：
G = \begin{cases} \sqrt{p} & \text{，当\ } p \equiv 1 \pmod{4} \text{，} \\ \mathrm{i} \sqrt{p} & \text{，当\ } p \equiv 3 \pmod{4} \text{，} \end{cases}
换句话说，
G^2 = p^{\star} := (-1)^{(p - 1) / 2} p \text{；}
以及对任意 r \ne 0，
\sum_{x \in \mathbb F_p} \omega^{r x^2} = \chi(r) G \text{。}
以上推导均在复数上进行。最终答案模 M = 998244353 计算，实际实现中我们将 G 视为满足 G^2 = p^{\star} 的形式元素，在二次扩环 \mathbb F_M[\sqrt{p^{\star}}] 中完成所有运算。
5. \operatorname{DFT} 与 \operatorname{IDFT} 在基下的表示
先求 \operatorname{DFT}(b_+)。当 r \ne 0 时，
\sum_{x \in R} \omega^{r x} = \frac{1}{2} \Biggl( -1 + \sum_{x} \omega^{r x^2} \Biggr) = \frac{1}{2} (-1 + \chi(r) G) \text{，}
当 r = 0 时其值为 \lvert R \rvert = \frac{p - 1}{2}。因此
\operatorname{DFT}(b_+) = \frac{p - 1}{2} \cdot b_0 + \frac{G - 1}{2} \cdot b_+ + \frac{-G - 1}{2} \cdot b_- \text{。}
对 \operatorname{IDFT} 同理，只需把 G 换成 \chi(-1) G。记
\varepsilon = \chi(-1) = (-1)^{(p - 1) / 2} \text{，}
则当 r \ne 0 时，
\sum_{x \in R} \omega^{-r x} = \frac{1}{2} (-1 + \varepsilon \chi(r) G) \text{，}
故
\operatorname{IDFT}(b_+) = \frac{p - 1}{2} \cdot b_0 + \frac{\varepsilon G - 1}{2} \cdot b_+ + \frac{-\varepsilon G - 1}{2} \cdot b_- \text{。}
再求 \operatorname{IDFT}(b_-)。当 r \ne 0 时，
\sum_{\substack{x \notin R \\ x \ne 0}} \omega^{-r x} = \frac{1}{2} \Biggl( -1 + 2 \sum_{x} \omega^{-r x} - \sum_{x} \omega^{-r x^2} \Biggr) = \frac{1}{2} (-1 - \varepsilon \chi(r) G) \text{，}
而当 r = 0 时其值为 \frac{p - 1}{2}。因此
\operatorname{IDFT}(b_-) = \frac{p - 1}{2} \cdot b_0 + \frac{-\varepsilon G - 1}{2} \cdot b_+ + \frac{\varepsilon G - 1}{2} \cdot b_- \text{。}
最后，
\operatorname{IDFT}(b_0) = \mathbf{1} = b_0 + b_+ + b_- \text{。}
6. 卷积幂公式
因为 b_0, b_+, b_- 是互不相交的指示函数，对它们做逐点幂时系数分别取幂，所以
\operatorname{DFT}(b_+)^{\odot k} = \biggl( \frac{p - 1}{2} \biggr)^k \cdot b_0 + \biggl( \frac{G - 1}{2} \biggr)^k \cdot b_+ + \biggl( \frac{-G - 1}{2} \biggr)^k \cdot b_- \text{。}
由线性性，
a_k = \frac{1}{p} \biggl[ \biggl( \frac{p - 1}{2} \biggr)^k \cdot \operatorname{IDFT}(b_0) + \biggl( \frac{G - 1}{2} \biggr)^k \cdot \operatorname{IDFT}(b_+) + \biggl( \frac{-G - 1}{2} \biggr)^k \cdot \operatorname{IDFT}(b_-) \biggr] \text{。}
记 \displaystyle T_\ell = \biggl( \frac{G - 1}{2} \biggr)^\ell + \biggl( \frac{-G - 1}{2} \biggr)^\ell。注意 T_0 = 2，T_1 = -1，并且 \displaystyle \biggl( \frac{G - 1}{2} \biggr) \biggl( \frac{-G - 1}{2} \biggr) = \frac{1 - G^2}{4} = \frac{1 - p^{\star}}{4}。
代入第 5 节中三个 \operatorname{IDFT} 的表达式，分别提取 b_0, b_+, b_- 的系数。
$$
\biggl( \frac{p - 1}{2} \biggr)^k + \frac{p - 1}{2} \biggl[ \biggl( \frac{G - 1}{2} \biggr)^k + \biggl( \frac{-G - 1}{2} \biggr)^k \biggr] = \biggl( \frac{p - 1}{2} \biggr)^k + \frac{p - 1}{2} \cdot T_k \text{。}
$$
$b_+$ 的系数：
$$
\biggl( \frac{p - 1}{2} \biggr)^k + \biggl( \frac{G - 1}{2} \biggr)^k \cdot \frac{\varepsilon G - 1}{2} + \biggl( \frac{-G - 1}{2} \biggr)^k \cdot \frac{-\varepsilon G - 1}{2} \text{。}
$$
$b_-$ 的系数：
$$
\biggl( \frac{p - 1}{2} \biggr)^k + \biggl( \frac{G - 1}{2} \biggr)^k \cdot \frac{-\varepsilon G - 1}{2} + \biggl( \frac{-G - 1}{2} \biggr)^k \cdot \frac{\varepsilon G - 1}{2} \text{。}
$$
下面按 $\varepsilon$ 的取值化简。
### 6.1 当 $p \equiv 1 \pmod 4
此时 \varepsilon = 1，p^{\star} = p。于是
\frac{\varepsilon G - 1}{2} = \frac{G - 1}{2} \text{，} \qquad \frac{-\varepsilon G - 1}{2} = \frac{-G - 1}{2} \text{。}
$$
\biggl( \frac{p - 1}{2} \biggr)^k + \biggl( \frac{G - 1}{2} \biggr)^{k + 1} + \biggl( \frac{-G - 1}{2} \biggr)^{k + 1} = \biggl( \frac{p - 1}{2} \biggr)^k + T_{k + 1} \text{。}
$$
$b_-$ 的系数变为
$$
\begin{aligned}
&\mathrel{\hphantom{=}} \biggl( \frac{p - 1}{2} \biggr)^k + \biggl( \frac{G - 1}{2} \biggr)^k \cdot \frac{-G - 1}{2} + \biggl( \frac{-G - 1}{2} \biggr)^k \cdot \frac{G - 1}{2} \\
&= \biggl( \frac{p - 1}{2} \biggr)^k
+ \frac{1 - p^{\star}}{4} \biggl[ \biggl( \frac{G - 1}{2} \biggr)^{k - 1} + \biggl( \frac{-G - 1}{2} \biggr)^{k - 1} \biggr] \\
&= \biggl( \frac{p - 1}{2} \biggr)^k + \frac{1 - p}{4} \cdot T_{k - 1} \text{。}
\end{aligned}
$$
所以
$$
a_k = \frac{1}{p} \biggl[ \biggl( \biggl( \frac{p - 1}{2} \biggr)^k + \frac{p - 1}{2} \cdot T_k \biggr) \cdot b_0 + \biggl( \biggl( \frac{p - 1}{2} \biggr)^k + T_{k + 1} \biggr) \cdot b_+ + \biggl( \biggl( \frac{p - 1}{2} \biggr)^k + \frac{1 - p}{4} \cdot T_{k - 1} \biggr) \cdot b_- \biggr] \text{。}
$$
### 6.2 当 $p \equiv 3 \pmod 4
此时 \varepsilon = -1，p^{\star} = -p。于是
\frac{\varepsilon G - 1}{2} = \frac{-G - 1}{2} \text{，} \qquad \frac{-\varepsilon G - 1}{2} = \frac{G - 1}{2} \text{。}
$$
\begin{aligned}
&\mathrel{\hphantom{=}} \biggl( \frac{p - 1}{2} \biggr)^k + \biggl( \frac{G - 1}{2} \biggr)^k \cdot \frac{-G - 1}{2} + \biggl( \frac{-G - 1}{2} \biggr)^k \cdot \frac{G - 1}{2} \\
&= \biggl( \frac{p - 1}{2} \biggr)^k + \frac{1 - p^{\star}}{4} \biggl[ \biggl( \frac{G - 1}{2} \biggr)^{k - 1} + \biggl( \frac{-G - 1}{2} \biggr)^{k - 1} \biggr] \\
&= \biggl( \frac{p - 1}{2} \biggr)^k + \frac{1 + p}{4} \cdot T_{k - 1} \text{。}
\end{aligned}
$$
$b_-$ 的系数变为
$$
\biggl( \frac{p - 1}{2} \biggr)^k + \biggl( \frac{G - 1}{2} \biggr)^{k + 1} + \biggl( \frac{-G - 1}{2} \biggr)^{k + 1} = \biggl( \frac{p - 1}{2} \biggr)^k + T_{k + 1} \text{。}
$$
因此
$$
a_k = \frac{1}{p} \biggl[ \biggl( \biggl( \frac{p - 1}{2} \biggr)^k + \frac{p - 1}{2} \cdot T_k \biggr) \cdot b_0 + \biggl( \biggl( \frac{p - 1}{2} \biggr)^k + \frac{1 + p}{4} \cdot T_{k - 1} \biggr) \cdot b_+ + \biggl( \biggl( \frac{p - 1}{2} \biggr)^k + T_{k + 1} \biggr) \cdot b_- \biggr] \text{。}
$$
以上公式对 $k \ge 1$ 都成立。实现时单独处理 $k = 0$：$a_0 = b_0$。
在计算时，若记 $\bigl( \frac{G - 1}{2} \bigr)^\ell = u_\ell + v_\ell G$，则有 $T_\ell = \operatorname{Tr} \bigl( \bigl( \frac{G - 1}{2} \bigr)^\ell \bigr) = 2 u_\ell$。所以每次查询只需在二次扩环中做一次快速幂。
## 7. 特殊情形 $p = M = 998244353
此时 p \equiv 1 \pmod 4，且 p^{\star} = p \equiv 0 \pmod M，第 6.1 节的公式中含有除以 p 的运算，而 p 在 \mathbb F_M 中不可逆，故不能直接使用。但因为 p \equiv 0，我们可以在模 p^2 意义下展开分子，再约去因子 p。
看作关于 p 和 G 的式子，利用二项式展开，
\begin{aligned}
\biggl( \frac{p - 1}{2} \biggr)^k &= \biggl( -\frac{1}{2} \biggr)^k + \frac{k p}{2} \biggl( -\frac{1}{2} \biggr)^{k - 1} + O(p^2) \text{，} \\
T_\ell &= \biggl( \frac{G - 1}{2} \biggr)^\ell + \biggl( \frac{-G - 1}{2} \biggr)^\ell \\
&= \biggl( -\frac{1}{2} \biggr)^\ell \sum_{j = 0}^{3} \binom{\ell}{j} (1^j + (-1)^j) G^j + O(G^4) \\
&= 2 \biggl( -\frac{1}{2} \biggr)^\ell + \ell (\ell - 1) p \biggl( -\frac{1}{2} \biggr)^\ell + O(p^2) \text{。}
\end{aligned}
将上述展开代入三个分子，常数项均因 1 + 2 \cdot \bigl( -\frac{1}{2} \bigr) = 0 而消失，留下的一次项分别为：
\begin{aligned}
N_0 &= \biggl( \frac{p - 1}{2} \biggr)^k + \frac{p - 1}{2} \cdot T_k \\
&= p \biggl( \frac{k}{2} \biggl( -\frac{1}{2} \biggr)^{k - 1} - \frac{1}{2} \cdot k (k - 1) \biggl( -\frac{1}{2} \biggr)^k + \frac{1}{2} \cdot 2 \biggl( -\frac{1}{2} \biggr)^k \biggr) + O(p^2) \\
&= p \biggl( -\frac{1}{2} \biggr)^{k + 1} (k^2 + k - 2) + O(p^2) \text{，} \\
N_+ &= \biggl( \frac{p - 1}{2} \biggr)^k + T_{k + 1} \\
&= p \biggl( \frac{k}{2} \biggl( -\frac{1}{2} \biggr)^{k - 1} + (k + 1) k \biggl( -\frac{1}{2} \biggr)^{k + 1} \biggr) + O(p^2) \\
&= p \biggl( -\frac{1}{2} \biggr)^{k + 1} (k^2 + 3 k) + O(p^2) \text{，} \\
N_- &= \biggl( \frac{p - 1}{2} \biggr)^k + \frac{1 - p}{4} \cdot T_{k - 1} \\
&= p \biggl( \frac{k}{2} \biggl( -\frac{1}{2} \biggr)^{k - 1} + \frac{1}{4} \cdot (k - 1) (k - 2) \biggl( -\frac{1}{2} \biggr)^{k - 1} - \frac{1}{4} \cdot 2 \biggl( -\frac{1}{2} \biggr)^{k - 1} \biggr) + O(p^2) \\
&= p \biggl( -\frac{1}{2} \biggr)^{k + 1} (k^2 - k) + O(p^2) \text{。}
\end{aligned}
因此除以 p 后得到
a_k(n) = \biggl( -\frac{1}{2} \biggr)^{k + 1} \begin{cases}
k^2 + k - 2 & \text{，当\ } n = 0 \text{；}\\
k^2 + 3 k & \text{，当\ } \chi(n) = +1 \text{；}\\
k^2 - k & \text{，当\ } \chi(n) = -1 \text{。}
\end{cases}
实现时，k 的多项式部分对 M 取模，指数 k + 1 对 M - 1 取模。
8. 代码实现
- 可用 O(\log p) 的 Jacobi 符号算法计算 \chi(n)。由于 p 是奇素数，Jacobi 符号就是 Legendre 符号，且不需要分解 p。
- 也可用 Euler 准则结合快速幂计算 \chi(n) \equiv n^{(p - 1) / 2} \pmod{p}。
- 若 p \ne M，则
- 若 p = M，直接使用第 7 节的公式。
在二次扩环 \mathbb F_M[\sqrt{p^{\star}}] = \mathbb F_M[G] / (G^2 - p^{\star}) 中，元素写作 a + b G，乘法为
(a + b G) (x + y G) = (a x + b y \cdot d) + (a y + b x) G \text{，}
其中
d = \begin{cases}
p \bmod M & \text{，当\ } p \equiv 1 \pmod 4 \text{，}\\
- p \bmod M & \text{，当\ } p \equiv 3 \pmod 4 \text{。}
\end{cases}
总时间复杂度为 $\mathcal O(Q (\log p + \log k))$。预处理“光速幂”可以得到更好的时间复杂度。
```cpp
#include <iostream>
#include <algorithm>
#include <bit>
using std::cin, std::cout;
#define F(i, a, b) for(int i = a; i <= (b); ++i)
void Solve();
int main() {
cin.sync_with_stdio(false);
cin.tie(nullptr);
Solve();
return 0;
}
using LL = long long;
const int Mod = 998244353;
const int Inv2 = (Mod + 1) / 2;
inline int qPow(int b, int e) {
int a = 1;
for (; e; e >>= 1, b = (int)((LL)b * b % Mod))
if (e & 1) a = (int)((LL)a * b % Mod);
return a;
}
inline int Jacobi(int a, int n) {
int s = 1;
while (a) {
int j = std::countr_zero((unsigned)a);
a >>= j;
if (j & (n >> 1 ^ n >> 2) & 1)
s = -s;
if (a == 1)
return s;
if (a < n) {
if (a & n & 2)
s = -s;
std::swap(a, n);
} else
a -= n;
}
return n == 1 ? s : 0;
}
int d;
struct D {
int a, b;
D() {}
D(int a_, int b_) : a(a_), b(b_) {}
friend D operator*(const D &p, const D &q) {
LL w = (LL)(p.a + p.b) * (q.a + q.b);
LL v = (LL)p.b * q.b;
LL x = (LL)p.a * q.a;
int rb = (int)((w - x - v) % Mod);
rb += rb >> 31 & Mod;
return D((int)((x + v % Mod * d) % Mod), rb);
}
};
int t, p, ip, b0, c;
D b1[4][1 << 16 | 7];
D qPow(LL e) {
D a(1, 0);
F(j, 0, 3) {
int k = e >> (j << 4) & ((1 << 16) - 1);
if (k)
a = a * b1[j][k];
}
return a;
}
void Solve() {
int q;
cin >> q >> p;
if (p == Mod) {
int totans = 0;
F(i, 1, q) {
LL k_; int k, n;
cin >> k_ >> n;
k = (int)(k_ % Mod);
int js = Jacobi(n, p);
int ans = (int)((LL)k * k % Mod);
ans = (int)(((LL)ans + (js == 0 ? k - 2ll + Mod : js == 1 ? 3ll * k : Mod - (LL)k)) % Mod);
ans = (int)((LL)ans * qPow(Mod - Inv2, (int)((k_ + 1) % (Mod - 1))) % Mod);
totans ^= ans;
}
cout << totans << '\n';
return ;
}
t = p >> 1 & 1;
d = t ? Mod - p % Mod : p % Mod;
ip = qPow(p % Mod, Mod - 2);
b0 = (p - 1) / 2 % Mod;
b1[0][1].a = Mod - Inv2;
b1[0][1].b = Inv2;
F(j, 0, 3) {
b1[j][0] = D(1, 0);
if (j)
b1[j][1] = b1[j - 1][1 << 16];
F(k, 2, 1 << 16)
b1[j][k] = b1[j][k - 1] * b1[j][1];
}
c = ((t ? (p + 1) / 2 % Mod : -(p - 1) / 2 % Mod) + Mod) % Mod;
int totans = 0;
F(i, 1, q) {
LL k; int n;
cin >> k >> n;
int js = Jacobi(n, p);
if (k == 0) {
totans ^= n == 0;
continue;
}
int ans = qPow(b0, (int)((k - 1) % (Mod - 1) + 1));
if (js == 0)
ans = (int)((ans + 2ll * qPow(k).a * b0) % Mod);
else if ((js == 1) == (t == 0))
ans = (int)((ans + 2ll * qPow(k + 1).a) % Mod);
else
ans = (int)((ans + (LL)qPow(k - 1).a * c) % Mod);
ans = (int)((LL)ans * ip % Mod);
totans ^= ans;
}
cout << totans << '\n';
}
```