题解：P17229 [Math×Girl²] 英雄变奏曲
Galois_Field_1048576
·
·
题解
声明: 写作过程中多次使用 AI 检验并修改病句、斟酌用词与行文,
论证的展开亦有 AI 参与;
思路均出自魔女の理团队的各出题人、验题人及我的个人理解.
约定. 根据个人习惯, 所有数组下标从 0 开始.
这可能影响你对奇数位置等术语的理解.
总结. 用连分数与分式线性变换把递归求和化为对 2A(N)+\Delta(N) 的计数; 经
Möbius 反演去掉互质条件后, 整除分块与树状数组逐块统计双曲线穿过的格点,
总复杂度 O(N\log^4 N).
题目描述. 利用 Euclid 算法定义 f(p,q): f(p,q)=\begin{cases}
0,&q\mid p;\\
k\left(\left\lfloor\frac pq\right\rfloor,\left\lfloor\frac q{p\bmod q}\right\rfloor\right)+f(q,p\bmod q),&\text{otherwise}.
\end{cases} 求 \sum_{\substack{1\le q<p\le N\\p\perp q}}f(p,q).
本题还额外保证 k(p,q) = g(p) h(q).
辗转相除法的处理
先回顾分式线性变换. 一个 2 \times 2 矩阵 \varphi = \begin{pmatrix}
a & b \\ c & d
\end{pmatrix} 按 \varphi z =\dfrac{az+b}{cz+d} 作用在数上,
称为分式线性变换或 Möbius 变换. 定义扩充复平面
$\varphi \infty = \dfrac ac$.
对于最简分数 $\dfrac pq$, 辗转相除法给出其连分数展开
$$\frac pq = a_0 + \frac 1{a_1 + \frac 1{a_2 + \frac1{\ddots}}} = [a_0; a_1, a_2, \dots].$$
取特殊矩阵 $T_k = \begin{pmatrix} k & 1 \\ 1 & 0 \end{pmatrix}$, 则有
$$\dfrac pq = T_{a_0} T_{a_1} \cdots T_{a_k} \infty.$$ 也就是说, 变换
$M = T_{a_0} T_{a_1} \cdots T_{a_k}$ 的矩阵第一列是
$\begin{pmatrix} p \\ q \end{pmatrix}$.
记 $\mathcal W$ 为所有可能出现的连分数构成的集合, 即由正整数组成且末项
$\ge2$ 的有限序列. 对 $w=(a_0,a_1,\ldots,a_n)\in\mathcal W$, 记
$M_w=T_{a_0}T_{a_1}\cdots T_{a_k}$. Euclid 算法告诉我们:
**定理 F.1.** 对于任意互质整数对 $1 \le q < p$, 存在唯一的 $w \in \mathcal W$, 使得
$$M_w \infty = \dfrac pq.$$
不难归纳证明, $f$ 的递归定义可以改写为
$$f(p, q) = \sum_{i=0}^{n-1} k(a_i, a_{i+1}).$$
现在把 $w\in\mathcal W$ 切成两段子序列 $w=st$. 设 $M_s=\begin{pmatrix}
x & X \\ * & *
\end{pmatrix}$, $M_t = \begin{pmatrix}
y & * \\ Y & *
\end{pmatrix}$ ($*$ 表示无关紧要的元素), 则 $M_w$ 的左上角元素为
$p = xy+XY$. 计算得 $M_s^\top \infty = \dfrac x X$; 又 $T_i$ 是对称矩阵,
故
$M_s^\top = T_{a_j}^\top \cdots T_{a_0}^\top = T_{a_j} \cdots T_{a_0}$,
从而 $\dfrac x X = [a_j; a_{j-1}, \dots, a_0]$, 于是
$a_j = \left\lfloor \dfrac xX \right\rfloor$, 而 $k(a_j, a_{j+1})$ 等于
$$k\left(\left\lfloor\dfrac{x}{X}\right\rfloor, \left\lfloor\dfrac{y}{Y} \right\rfloor\right),$$
同时 $p \le N$ 的条件变为 $xy+XY \le N$, 故答案为
$$\sum_{\substack{M_s\ \text{首行为}\ (x,X) \\ M_t\ \text{首列为}\ (y,Y)^\top}} k\left(\left\lfloor\dfrac{x}{X}\right\rfloor, \left\lfloor\dfrac{y}{Y} \right\rfloor\right).$$
表面上看, 需要分别处理首行 $(x,X)$ 与首列 $(y,Y)^\top$,
但二者可由转置互相转化. 由此猜测答案为
$$2 A(N), \text{其中}\ A(N) = \sum_{\substack{x > X > 0, x \perp X \\ y > Y > 0, y \perp Y \\ xy + XY \le N}} k\left(\left\lfloor\dfrac{x}{X}\right\rfloor, \left\lfloor\dfrac{y}{Y} \right\rfloor\right)$$
因子 $2$ 的来源是: 分解 $w = st$ 时, $s$ 可能属于 $\mathcal W$,
也可能不属于 (即 $s$ 的末项为 $1$). 连分数有恒等式
$[a_0;a_1,\dots,a_n] = [a_0;a_1,\dots,a_n-1,1]$,
故存在保持连分数值的双射
$\mathcal W \leftrightarrow \text{以 } 1 \text{ 结尾的连分数}$, 两类 $s
的贡献大致相同, 统一按 s \in \mathcal W 计算后乘 2 即得正确结果.
备注. 这一备注写给对“为何只有两种表示”有疑问的读者. 设
p & p' \\ q & q'
\end{pmatrix}$ 由 $T_k$ 的乘积组成. 由于 $|T_k| = -1$, 必有
$|M| = \pm 1$; 又易归纳证明 $0 \le p' < p$, $0 \le q' < q$. 细想之下,
线性不定方程 $pq' - p'q = \varepsilon$ ($\varepsilon \in \{-1,1\}$) 在
$0 \le p' < p$, $0 \le q' < q$ 的约束下恰有两组解, 正是
$[a_0;a_1,\dots,a_n] = [a_0;a_1,\dots,a_n-1,1]$ 对应的两种表示.
然而这个猜想并不完全正确. 上文说两类 $s$ 的贡献*大致*相同, 这是因为当
$s$ 的长度 $\ge 2$ 时, $\dfrac x X$ 对应的计数对象是 $s^{\text{反转}}$,
而 $s^{\text{反转}}$ 末位的 $m \hookrightarrow m-1, 1$ 修改的是 $s
的首位, 不影响 s 的末项, 也就不影响贡献. 唯一的偏差出现在 |s| = 1
时, 此时 [m-1;1] = m = [m], 即 X = 1, 2A(N) 中计入了
为此引入修正项
$$\Delta(N) = \sum_{\substack{x \ge 1 \\ xy + Y \le N}} k\left(x-1, \left\lfloor\dfrac{y}{Y} \right\rfloor\right) - k\left(x, \left\lfloor\dfrac{y}{Y} \right\rfloor\right).$$
这里还有一处细节: $A(N)$ 中完全没有 $x = X = 1$ 的项,
而真实求和中它出现了一次. 为了让 $k(x - 1, \cdots) - k(x, \cdots)
这一公式仍然生效, 需要令 k(0, \cdots) = 2 k(1, \cdots). 整理可得
\Delta(N) = \sum_{\substack{y>Y\ge1\\y \perp Y\\y+Y\le N}} k\left(0, \left\lfloor\frac yY\right\rfloor\right) - k\left(\left\lfloor\frac{N-Y}{y}\right\rfloor, \left\lfloor\frac yY\right\rfloor\right).
(这里的 y + Y \le N 是为了保证
至此, 我们严谨地得到答案为 $2 A(N) + \Delta(N)$.
## 算法
用 Möbius 反演去掉互质条件:
$$[x \perp X\ \text{且}\ y \perp Y] = \sum_{\substack{d \mid x \\ d \mid X \\ e \mid y \\ e \mid Y}} \mu(d) \mu(e),$$
交换求和顺序, 定义去掉互质条件后的辅助计数函数
$$F_{\rm free}(N) = \sum_{\substack{x > X > 0 \\ y > Y > 0 \\ xy + XY \le N}} k\left(\left\lfloor\dfrac{x}{X}\right\rfloor, \left\lfloor\dfrac{y}{Y} \right\rfloor\right),$$
则
$$A(N) = \sum_{d, e} \mu(d) \mu(e) F_{\rm free}\left(\left\lfloor \dfrac N{de} \right\rfloor\right) = \sum_{t} (\mu * \mu)(t) F_{\rm free}(\lfloor N/t \rfloor).$$
至此, 只需计算 $F_{\rm free}$ 在整除分块给出的 $\mathrm O(\sqrt N)
个取值处的值.
自然地, 枚举 a = \left\lfloor\dfrac{x}{X}\right\rfloor,
几何上看, 这相当于统计矩形 $R = [aX, (a+1)X) \times [bY, (b+1)Y)
与双曲线下方区域 P = \{(u, v) : uv \le N-XY\} 的交中的格点数.
多数矩形的格点要么全在 P 内, 要么全在 P 外, 被双曲线穿过的只有满足
满足条件的块是 $(a, b) = (a_0, 1)$ 到 $(a, b) = (1, b_0)$
之间一条格点路径的子集, 路径长度恰为 $(a_0, 1)$ 与 $(1, b_0)$
的网格距离, 即 $a_0 + b_0 - 2$. 而 $a_0 \cdot 1$ 与 $1 \cdot b_0$ 都接近
$\dfrac{N}{XY}$, 故值得一算的块只有
$\mathrm O\left(\dfrac{N}{XY}\right)$ 个. 再对 $X, Y$ 求和:
$$\sum_{XY \le N} \dfrac{N}{XY} \le N \left(\sum_{X \le N} \dfrac 1X\right)^2 = \mathrm O(N \log^2 N).
对每个块再按行分类: 整行合法、整行非法, 或双曲线穿过该行.
前两类可直接处理; 对于第三类, 需要查询形如
用支持单点修改和区间查询的树状数组维护.
由于操作结果只与 $M = N-XY$ 有关, 与 $N$ 本身关系不大, 故按 $M = N-XY
离线处理: 对事件 (M; T, X, Y), 当扫描到 M = T-XY 时, 把块 (X, Y)
的贡献累加到 F(T) 中. 固定 T 时, 对应事件的块数为
$$\text{总块数} \le \sum_{d \le \sqrt N} \mathrm O\left(\dfrac{N}{d} \log^2 N\right) + \sum_{d \le \sqrt N} \mathrm O(d \log^2 d) = \mathrm O(N \log^3 N).$$
每个块查询一次树状数组, 总复杂度为 $\mathrm O(N \log^4 N)$.
当 $M$ 增加到 $M+1$ 时,
$\left\lfloor\dfrac {M+1}x\right\rfloor - \left\lfloor\dfrac Mx\right\rfloor = [(M+1) \bmod x = 0]$,
换言之, 每次 $M \to M + 1$ 要做 $\mathrm d(M+1)$ 次单点更新,
总更新次数为 $\mathrm O(N \log N)$, 这些更新的总时间为
$\mathrm O(N\log^2 N)$.
询问次数 $\mathcal Q=\mathrm O(N\log^3N)$ 与修改次数
$\mathcal M=\mathrm O(N\log N)$ 并不同阶, 因而树状数组或 $2
叉线段树并非理论上渐近最优. 若用 \log N 叉线段树, 查询为
$O\left(\dfrac{\log^2N}{\log\log N}\right)$, 总时间可降至
$O\left(\dfrac{\log^4N}{\log\log N}\right)$.
最后是边界修正的计算: 先用 Möbius 反演去掉互质限制. 由于
$k(p,q) = g(p) h(q)$, 可用 Abel 求和变换写出形如
$$\sum_d \mu\left(\dfrac{N}{d}\right)\sum_{2Y+1 \le d} \sum_{x=1}^{L_x} \Delta g(x) \cdot \sum_{y=Y+1}^{L_y(x)} h\left(\left\lfloor \dfrac{y}{Y} \right\rfloor\right)$$
的和式, 内层和用 $h$ 的前缀和 $\mathrm O(1)$ 求出; $\sum_Y \sum L_x
的项数为 \mathrm O(d \log d), 故整体时间为 \mathrm O(N \log^2 N),
可以快速计算.