# 网格生存概率: 题解

出题人解法：统计安全路径数，滚动递推，最后统一除以等概率过程总数。Codex（GPT-6）整理扁平存储及标准 C++17 的防溢出模乘，并补充稀疏道路图方案。

## 先计数，最后转成概率

令 $D_t(x,y)$ 表示从任意道路起点出发、走 $t$ 步、全程安全且终止于 $(x,y)$ 的过程数。初始时，道路的值为一，坑洞的值为零。道路位置的新值等于上下左右四邻居旧值之和；坑洞和网格外始终按零处理。

每条非空安全过程都有唯一的最后一步。删除这一步，会得到从某个邻居结束的安全过程；反过来，邻居的安全过程可以唯一扩展到当前道路。因此递推既不遗漏也不重复。归纳后，$A=\sum_{x,y}D_k(x,y)$ 就是安全过程总数。每个起点和方向串的选择概率相同，答案为 $A/(nm\cdot4^k)$ .

只保存相邻两轮数组。每轮覆盖全部道路的新值；坑洞的两个存储层都保持零。判断是否为道路必须使用网格字符，不能把当前计数为零当作永久障碍。

## 数值范围与模运算

对固定终点，每个反向方向串至多对应一个起点，因此 $D_t(x,y)\le4^t\le2^{50}$ .本题每格的精确计数都能放入 64 位整数，无需在内层递推取模。最终总和可能超出 64 位范围，逐格加入并取模即可：每次被加数至多 $2^{50}$ ，部分和小于 $P$ ，两者相加安全。

分母在模 $P$ 下非零，因为 $1\le nm<P$ ，且 $P$ 为奇质数。用费马小定理求逆元 $q^{P-2}\bmod P$ .两个余数直接相乘可能溢出；程序的模乘按乘数二进制逐位累加和倍增，每次相加小于 $2P<2^{54}$ ，只使用标准 64 位整数。快速幂建立在这个模乘上，不依赖编译器扩展整数。

## 复杂度与并列方案

令 $B=\lceil\log_2 P\rceil$ 为模数位数。递推和输入共 $O(nm(k+1))$ 时间，归一化的模幂用 $O(B^2)$ 次固定宽度整数操作，总时间 $O(nm(k+1)+B^2)$ ，空间 $O(nm)$ .

[std.cpp](std.cpp) 使用出题人的网格滚动递推。对于道路很少的网格，[稀疏道路图](solution-alternative.zh.md)把每轮工作降到道路数，只需保存道路之间的相邻关系。它在满网格中存储更多信息，作为有不同适用形状的并列方案；两份程序都覆盖完整范围。