官方题解只能做到 $O(qm^3 \log n)$？玩的太差了。这题可以把官方的 $O(qm^3\log n)$ 做法进一步优化：线性规模预处理，单次修改和非退化查询均为 $O(m^2\log(2+n/m))$，空间为 $O(nm)$。关键不只是维护转移矩阵，而是同时利用“单点修改是秩一修改”“查询只需要矩阵乘向量”和“根节点的线性系统可以动态维护”。官方题解采用按行转移、线段树维护矩阵积，并在查询时解小规模方程组。 实现还处理了一个容易忽略的细节：约分后的答案在模意义下有定义，不代表直接建立的模线性方程组一定非奇异。下面先讲快速算法，再说明这部分。
题解
题目给出一个首尾相接的 $n\times m$ 网格，修改某个格子的四个转移概率，询问从 $S$ 第一次到达 $T$ 的期望步数。其中 $n\le 10^5$、$3\le m\le 5$、$q\le 3\cdot 10^4$，答案对 $P=10^9+7$ 取模。([QOJ][2])
设 $F_{i,j}$ 表示从 $(i,j)$ 第一次到达当前目标的期望。除目标外，每个格子都满足 $100F_{i,j}=\ell_{i,j}F_{i,j-1}+r_{i,j}F_{i,j+1}+u_{i,j}F_{i-1,j}+d_{i,j}F_{i+1,j}+100$，行列下标分别按 $n,m$ 取模。
由于 $d_{i,j}$ 非零，可以把下一行解出来：
$F_{i+1,j}=(100F_{i,j}-\ell_{i,j}F_{i,j-1}-r_{i,j}F_{i,j+1}-u_{i,j}F_{i-1,j}-100)/d_{i,j}$。
因此，只要知道相邻两行的值，就可以推出下一行。令 $D=2m$，把状态定义为 $Z_i=(F_{i,0},\ldots,F_{i,m-1},F_{i-1,0},\ldots,F_{i-1,m-1},1)^T$。那么第 $i$ 行对应一个 $(D+1)\times(D+1)$ 的仿射转移矩阵 $T_i$，满足 $Z_{i+1}=T_iZ_i$。
这个矩阵非常稀疏：前 $m$ 行各有常数个非零元素，随后 $m$ 行负责复制当前行，最后一行保持常数 $1$。因此，单行转移乘一个向量只要 $O(m)$，单行转移左乘一个完整矩阵只要 $O(m^2)$。
记一整圈的转移为 $Q=T_{n-1}\cdots T_0$，将其写成 $Q=\begin{pmatrix}A&b\\0&1\end{pmatrix}$。线段树负责维护这个矩阵积。
先处理“目标的方程不能使用”，但不立即加入目标值为零的约束。
设目标是 $(t_x,t_y)$。我们仍使用原来的 $T_{t_x}$，只是在转移结束后允许增加一个自由变量 $h$：
$Z_{t_x+1}=T_{t_x}Z_{t_x}+h e_{t_y}$。
这里 $e_{t_y}$ 是对应下一行第 $t_y$ 个格子的单位向量，常数维为零。这样恰好取消了目标处原来的期望方程：不论那个方程原本算出什么值，都可以通过 $h$ 调整为真正需要的值，其他格子的方程不受影响。
令 $g=T_{n-1}\cdots T_{t_x+1}e_{t_y}$。如果 $x$ 表示初始状态 $Z_0$ 的前 $D$ 个分量，那么绕一圈后的状态是 $Ax+b+gh$。网格首尾相接，所以必须满足 $(A-I)x+gh=-b$。
目前有 $D$ 个方程、$D+1$ 个未知量，多出来的自由度是什么？
正是整体加上同一个常数。所有非目标方程都不变，因为四个转移概率之和为 $1$。所以我们可以暂时固定 $x_0=0$，不要求目标值为零。最后输出算出的 $F_S-F_T$，就会恢复正确的目标边界条件。
从 $A-I$ 中删去第 $0$ 列，得到一个 $D\times(D-1)$ 的矩阵 $B$；记 $y=(x_1,\ldots,x_{D-1})^T$、$f=-b$。查询就变成了求解：
$$ By+gh=f. $$
这是整个算法最重要的化简：只要没有修改，所有查询的 $B,f$ 都相同，只有向量 $g$ 随目标变化。
求出 $y,h$ 后恢复 $Z_0$，再沿转移计算起点、终点的值即可。若 $s_x\le t_x$，先走到第 $s_x$ 行记录起点值，再走到第 $t_x$ 行记录目标值；若 $s_x>t_x$，先走到目标所在行记录目标值，执行一次 $T_{t_x}$ 并加入 $h e_{t_y}$，然后继续走到起点。最后都取两者之差。同一行但不同列的情况也自然包含在内。
整个查询只需要常数次“区间矩阵积作用于一个向量”，不需要把这些区间的完整矩阵乘出来。
修改也不需要重新做完整矩阵乘法。
修改 $(i,j)$ 的概率，只改变 $T_i$ 的第 $j$ 行，所以必然可以写成 $T_i'=T_i+uv^T$，其中最初的 $u=e_j$，$v^T$ 是这一行的新旧差值。
假设一个线段树节点维护 $M=M_RM_L$。如果左儿子发生秩一变化 $M_L'=M_L+uv^T$，则父节点的变化为 $M'=M+(M_Ru)v^T$；如果右儿子发生变化，则为 $M'=M+u(v^TM_L)$。
因此，沿修改路径向上时，只需维护两个向量。每层进行一次矩阵乘向量，再把一个外积加到已有矩阵上，都是 $O(m^2)$，而不是 $O(m^3)$。
同理，根节点变化后，删去固定列得到的 $B$ 也只发生秩一变化。于是，接下来要解决的是：怎样在 $O(m^2)$ 内更新 $B$ 的线性系统，而不在每次查询时重新高斯消元？
动态维护秩分解，去掉最后一次三次消元。
维护两个可逆矩阵 $L,R$，以及当前秩 $\rho$，使得 $LBR=J_\rho$，其中 $J_\rho$ 是一个 $D\times(D-1)$ 的矩阵，前 $\rho$ 个对角元素为 $1$，其他位置全为零。
在非退化查询中，$\rho=D-1$。记 $a=Lg$、$c=Lf$，并令 $z=R^{-1}y$，则查询方程变成 $J_{D-1}z+ah=c$。
最后一行没有 $z$，直接得到 $h=c_{D-1}/a_{D-1}$；前面的各行给出 $z_i=c_i-a_i h$，最后算出 $y=Rz$ 即可。向量 $c=Lf$ 可以在每次修改后预先算好，所以查询只需矩阵乘向量和一次求逆，总共 $O(m^2)$。
下面说明这个分解为什么能在秩一修改后用 $O(m^2)$ 维护，而不是把复杂度藏在某次重建中。
若 $B'=B+uv^T$，则 $LB'R=J_\rho+ab^T$，其中 $a=Lu$、$b^T=v^TR$。我们只需要把“矩形单位矩阵加一个外积”重新化成标准形。
如果 $a$ 在第 $\rho$ 行及之后有非零分量，就可以利用 $J_\rho$ 的一个零行，把 $a$ 的所有非零分量集中到这一行。这只需一次换行、一次行缩放以及 $O(m)$ 次行加法。此时新增内容全部落在这一行中，再用已有的单位行消去前 $\rho$ 列；剩余部分非零就新增一个主元，否则秩不变。若只有 $b$ 在非主元列中非零，则对称地进行列操作。
如果 $a,b$ 都完全位于已有的主元部分，问题就只剩 $I+ab^T$。令 $\delta=1+b^Ta$。当 $\delta\ne0$ 时，利用 $(I+ab^T)^{-1}=I-ab^T/\delta$，一次外积更新即可完成；当 $\delta=0$ 时，秩恰好下降一，再进行 $O(m)$ 次行列操作，把减少的那个主元移出主元区。
每次行操作只需要同步修改 $L$ 的一行，每次列操作只需要同步修改 $R$ 的一列，单次操作都是 $O(m)$。总共只有 $O(m)$ 次这样的操作，所以维护分解的复杂度为 $O(m^2)$。这也覆盖了修改过程中的临时降秩，不需要假设某个固定补全矩阵永远可逆。
预处理还可以再省掉一个 $m$。
如果直接为每一行建立一个线段树叶子，建树仍然需要 $O(nm^3)$。我们把连续 $\Theta(m)$ 行组成一块，只对这些块建立线段树。
一块的矩阵从单位矩阵开始，依次左乘其中各行的稀疏转移。每行只需 $O(m^2)$，所有块合计 $O(nm^2)$。块的数量为 $O(n/m+1)$，在线段树内部做完整矩阵乘法的总成本也只有 $O(nm^2+m^3)$。
修改时，先在所在块内用稀疏转移算出该块的秩一变化，再沿线段树向上传递。查询时，两端不足一整块的部分逐行作用于向量，中间整块在线段树上处理。两端各只有 $O(m)$ 行，所以这部分仍为 $O(m^2)$。
正确性、复杂度与模数退化
正确性可以串成一条完整的对应关系：单行转移与非目标格子的期望方程等价；自由变量 $h$ 恰好取消目标处的一个方程；整圈状态相等恰好保证纵向首尾相接；固定 $x_0=0$ 只消除了整体平移的自由度；最后减去目标值，又恢复了 $F_T=0$。因此，恢复出来的函数满足原题全部期望方程，输出就是所求的首次到达期望。
线段树的秩一更新是矩阵乘法分配律的直接展开，动态分解则始终保持 $LBR=J_\rho$，不会改变线性系统的解。因此，上述优化不会改变答案。
将固定模数下的域运算计为常数，快速路径的总复杂度为 $O(nm^2+m^3+qm^2\log(2+n/m))$，空间为 $O(nm+m^2)$。在本题 $n\ge3,m\le5$ 的范围内，可以分别简写为 $O(nm^2+qm^2\log(2+n/m))$ 和 $O(nm)$。若把快速幂求逆单独计算，还需加上 $O((q+m)\log P)$。
固定 $m\le5$ 后，就是线性预处理、对数时间操作。与官方方法相比，预处理和每次操作中对 $m$ 的依赖均降低了一阶。输入规模给出的下界是 $\Omega(nm+q)$，但这个下界本身并不能证明动态操作的对数项不可去掉。
这里还有一个必须单独说明的严谨性问题。题面承诺的是：答案约分后的分母与 $P$ 互质。这不能直接替换成“我们列出的方程组模 $P$ 非奇异”这一承诺。例如整数方程 $Px=P$ 的答案显然是 $1$，但直接取模后只剩 $0=0$。原题的输出保证确实是对约分后的答案作出的。([QOJ][2])
因此，完整代码没有在检测到奇异系统时直接报错或随意给自由变量赋值，而是使用了精度提升的后备路径。
设当前查询的方阵为 $C=[B\mid g]$，未知向量为 $w=(y,h)$，并把最终输出写成 $\lambda^Tw+\lambda_0$。通过行列式恒等式，可以将答案写成 $N/\Delta$，其中 $\Delta=\det C$，而 $N$ 可以用 $\lambda_0\Delta$ 减去一个增广行列式得到：在 $C$ 的右侧添加列 $f$，底部添加行 $\lambda^T$，右下角填 $0$。
后备路径改在模 $P^k$ 下维护同样的转移矩阵，先取 $k=2$，精度不足时翻倍。设 $\Delta$ 含有 $v$ 个因子 $P$，只要 $k>v$，就可以同时约掉 $N,\Delta$ 中的 $P^v$，然后再对 $P$ 求商。所有单行转移的分母都是输入中的 $d_{i,j}< P$，因此在每个模 $P^k$ 的环中都可逆。
高精度矩阵仍然用分块线段树和秩一修改维护，不会每个退化查询都扫描整个网格。行列式计算中只对与 $P$ 互质的主元求逆；当剩余子矩阵的所有元素都含有 $P$ 因子时，先提取这些因子，并相应调整计算精度。
这部分的成本还取决于实际需要的 $k$：区间操作仍然是 $O(m^2\log(2+n/m))$ 次相应精度的算术运算，但还会有小型行列式、单位逆元和因子提取的大整数开销；精度提升时需要重建高精度树。因此，不能把包含任意可约退化情况的完整实现，无条件地标成固定字长下的 $O(n+q\log n)$。前面的界适用于不需要精度提升的快速路径，完整源码则额外覆盖了题面文字保证下的退化情况。