Survival on a Grid: Solution¶
Problem setter’s solution: count safe paths with rolling DP, then divide once by the number of equally likely processes. Codex (GPT-6) supplies flat storage, portable C++17 modular multiplication without overflow, and the sparse-road alternative.
Count first and normalize last¶
Let \(D_t(x,y)\) count processes that start at any road cell, take \(t\) steps, remain safe, and end at \((x,y)\) . Initially a road cell has value one and a pit has value zero. A road cell's next value is the sum of the previous values of its four neighbors. Pits and positions outside the grid always contribute zero.
Every nonempty safe process has a unique final step. Removing it gives a safe process ending at a neighbor; conversely, each such neighbor process extends uniquely to the current road cell. Thus the recurrence neither omits nor duplicates a process. By induction, \(A=\sum_{x,y}D_k(x,y)\) is the number of safe processes. All start-and-direction strings are equally likely, giving probability \(A/(nm\cdot4^k)\) .
Store just two consecutive rounds. Overwrite every road value on each round, while both layers remain zero at pits. Use the grid character to recognize roads: a current count of zero does not make a cell a permanent obstacle.
Numeric bounds and modular arithmetic¶
For a fixed endpoint, each reversed direction string determines at most one starting cell. Hence \(D_t(x,y)\le4^t\le2^{50}\) . Every exact cell count fits 64-bit integers, so the inner recurrence needs no modular reductions. The total may exceed 64-bit range. Accumulate it modulo \(P\) one cell at a time: the partial remainder is below \(P\) and the next count at most \(2^{50}\) , so each addition is safe.
The denominator is nonzero modulo \(P\) because \(1\le nm<P\) and \(P\) is an odd prime. Fermat's little theorem gives the inverse as \(q^{P-2}\bmod P\) . Direct multiplication of two residues can overflow. The program instead processes multiplier bits, using modular addition and doubling. Each addition is below \(2P<2^{54}\) , so standard 64-bit integers suffice. Binary exponentiation uses this multiplication and needs no extended integer type.
Complexity and parallel method¶
Let \(B=\lceil\log_2 P\rceil\) be the modulus bit length. Reading and DP take \(O(nm(k+1))\) time. Normalization takes \(O(B^2)\) fixed-width integer operations, so total time is \(O(nm(k+1)+B^2)\) with \(O(nm)\) space.
std.cpp uses the setter's rolling grid DP. On grids with few roads, the sparse-road method restricts each round to road cells and stores only their adjacency. It stores more information on a full grid, so it is a parallel method suited to different input shapes. Both programs cover the full range.