# 病毒狙击手：题解

## 解法比较

出题人解法的线性期望转移矩阵可以描述传播过程。计算矩阵幂时，不能直接将步数对 $P-1$ 取模：费马小定理关于非零域元素的结论不适用于任意矩阵。

例如在模素数 $P$ 下取 $H=\begin{pmatrix}1&1\\0&1\end{pmatrix}$ ，则 $H^t=\begin{pmatrix}1&t\\0&1\end{pmatrix}$ .当 $t=P-1$ 时它不是单位矩阵，而先取模会把指数变成零。这种矩阵也对应“已有数量保留、同时给下一层增加数量”的传播结构。因此必须正确处理完整指数。

矩阵模型的一种直接计算方法是对完整的大整数指数做矩阵快速幂：指数有 $b$ 个二进制位、矩阵维数为 $d$ 时，每个指数需 $O(bd^3)$ 次域运算及 $O(d^2+b)$ 空间。Codex（GPT-6）采用的实现进一步用特征多项式约化矩阵幂，多项式阶段每位为 $O(d^2)$ ，另需预处理和恢复矩阵的开销；完整复杂度见下文。优势是正确处理完整指数并减少反复矩阵乘法，代价是多项式预处理与更复杂的实现。

## 初值和期望转移

用二维差分处理 $Q$ 次矩形加法，再做二维前缀和，得到整个试验场的初始强度。原始强度不超过 $10^{15}$ ，中间累加使用 64 位整数。

以下运算均在模素数 $P=1000000009$ 的域中进行。分母满足 $1\le b<P$ ，所以概率可表示为 $a b^{P-2}\bmod P$ .令 $v_t$ 为 $d=NM$ 个格子的期望组成的行向量，构造转移矩阵 $H$ ：对角线先加 $1$ 以保留当前强度，再将来源格 $i$ 向目标格 $j$ 的概率加到 $H_{ij}$ .越界方向忽略。

传播事件独立于当前强度，结合期望的线性性得到

$$v_{t+1}=v_tH,\qquad v_T=v_0H^T$$

不能把矩阵指数直接对 $P-1$ 取模。比如 $H=\begin{pmatrix}1&1\\0&1\end{pmatrix}$ 满足 $H^T=\begin{pmatrix}1&T\\0&1\end{pmatrix}$ ，其非对角项取决于 $T\bmod P$ .此外，合法输入也可能给出奇异矩阵。

## 求特征多项式

记

$$f(x)=\det(xI-H)=x^d+c_1x^{d-1}+\cdots+c_d$$

先逐次乘矩阵，算出 $I,H,\ldots,H^d$ ，并取得 $s_j=\operatorname{tr}(H^j)$ .由 Newton 恒等式，令 $c_0=1$ ，有

$$c_k=-k^{-1}\sum_{j=1}^{k}c_{k-j}s_j\pmod P\qquad(1\le k\le d)$$

因为 $d\le50<P$ ，这里所有 $k$ 都可求逆。实现保留矩阵幂，计算量为 $O(d^4)$ ；本题至多约 $6.25\times10^6$ 次矩阵乘加项，足够使用。

## 用多项式处理完整的大指数

Cayley–Hamilton 定理给出 $f(H)=0$ .因此若

$$x^T\bmod f(x)=r_0+r_1x+\cdots+r_{d-1}x^{d-1}$$

则

$$H^T=\sum_{j=0}^{d-1}r_jH^j$$

两个次数小于 $d$ 的多项式先卷积，再从高次向低次利用

$$x^d\equiv-c_1x^{d-1}-\cdots-c_d\pmod {f(x)}$$

消去所有高次项，每次乘法耗时 $O(d^2)$ .

将输入的十进制字符串反复除以 $2$ ，取得完整二进制位；预计算 $x^{2^j}\bmod f(x)$ ，所有询问共享。按置位相乘得到余式。整个过程没有丢弃指数信息，适用于奇异矩阵和重复特征根。$T=0$ 时余式为常数 $1$ ；$d=1$ 时先把 $x$ 化为模一次多项式的常数。

## 按顺序回答询问

从初值表提取当前矩形的行向量 $v_0$ ，利用保存的 $H^j$ 计算

$$v_T=\sum_{j=0}^{d-1}r_j(v_0H^j)$$

输出归一化到 $[0,P-1]$ 的各项，再以 64 位整数求它们的和 $S$ .注意 $S$ 不再对 $P$ 取模。按题面公式更新区域起点，下一次仍读取同一份初值表。

## 正确性

二维差分准确恢复全部矩形更新后的初值。转移矩阵逐项表示“保留原值加上所有来源的期望贡献”，因此 $v_T=v_0H^T$ .Newton 恒等式求出 $H$ 的特征多项式，Cayley–Hamilton 定理保证多项式余式替代 $H^T$ 不改变结果。二进制快速幂使用完整指数，得到正确余式。最后按输出值更新区域，并为下一场恢复初值，故所有询问均符合定义。

## 复杂度

令 $L$ 为最大输入时刻的十进制位数，$b=O(L)$ 为最大二进制位数。矩阵幂与特征多项式预处理为 $O(d^4)$ ，共享多项式幂为 $O(bd^2)$ .每个询问需要 $O(L^2+bd^2+d^3)$ 时间，其中 $O(L^2)$ 来自字符串除法。总时间为

$$O(Q+AB+d^4+bd^2+K(L^2+bd^2+d^3))$$

空间为 $O(AB+d^3+bd+L)$ .所有模乘都在 64 位有符号整数范围内；$7S<7dP$ 也不会溢出。