病毒狙击手：题解¶

解法比较¶

出题人解法的线性期望转移矩阵可以描述传播过程。计算矩阵幂时，不能直接将步数对 \(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\) 也不会溢出。