网格生存概率: 题解¶

出题人解法：统计安全路径数，滚动递推，最后统一除以等概率过程总数。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 使用出题人的网格滚动递推。对于道路很少的网格，稀疏道路图把每轮工作降到道路数，只需保存道路之间的相邻关系。它在满网格中存储更多信息，作为有不同适用形状的并列方案；两份程序都覆盖完整范围。