题解

思路推导

一条最短路径只会向下或向右。若它经过了 $t$ 个异常格，终点电量只由 $t$ 决定，记为

$$f(t)=\left\lceil\frac{s}{2^t}\right\rceil.$$

关键困难是只给出至多两千个异常格，不能在整个网格上做动态规划。

对于两个格子 $a=(r_1,c_1)$、$b=(r_2,c_2)$，若 $r_1\le r_2$ 且 $c_1\le c_2$，从 $a$ 到 $b$ 的最短路径数为

$$W(a,b)=\binom{r_2-r_1+c_2-c_1}{r_2-r_1};$$

否则为零。阶乘和逆阶乘可以在 $O(n+m)$ 时间内预处理。

把每个异常格看成一个权值为形式变量 $x$ 的格子，则所有路径的生成函数中，$x^t$ 的系数就是恰经过 $t$ 个异常格的路径数。使用恒等式 $x=1+(x-1)$，可以按“被选中的异常格链”展开生成函数。

设 $A_i(x)$ 表示从起点到异常格 $i$、但尚未给 $i$ 乘上 $x$ 时的路径生成函数。按坐标排序后有

$$A_i(x)=W((1,1),i)+\sum_{j<i}(x-1)A_j(x)W(j,i),$$

其中不可达的 $j$ 自动贡献零。终点的生成函数同理为

$$F(x)=W((1,1),(n,m))+\sum_i(x-1)A_i(x)W(i,(n,m)).$$

做法

直接保存完整多项式需要三次方复杂度。注意 $s\le10^6$，令 $L$ 为满足 $2^L>s-1$ 的最小整数，则 $L\le20$，并且对所有 $t\ge L$ 都有 $f(t)=1$。

因此只需保存多项式的 $0$ 次至 $L-1$ 次系数，以及所有次数不小于 $L$ 的系数之和。若当前压缩向量为

$$(p_0,p_1,\ldots,p_{L-1},p_{\ge L}),$$

乘以 $x-1$ 后的新向量为

$$(-p_0,p_0-p_1,\ldots,p_{L-2}-p_{L-1},p_{L-1}).$$

最后一项来自高次系数的望远镜求和，所以压缩表示在乘以 $x-1$ 后仍然封闭。

依次计算每个 $A_i$ 的压缩向量，再用同样的转移得到终点分布。答案分子为

$$\sum_{t=0}^{L-1}[x^t]F(x)f(t)+[x^{\ge L}]F(x),$$

最后除以总路径数 $W((1,1),(n,m))$。

正确性证明

对任意固定路径，设它经过的异常格集合为 $S$。在所有异常格链的展开中，从该路径上的异常格选出任意子集都会贡献一次，对应权值 $(x-1)^{|T|}$。这些贡献之和为

$$\sum_{T\subseteq S}(x-1)^{|T|}=(1+x-1)^{|S|}=x^{|S|}.$$

因此递推得到的 $F(x)$ 的 $t$ 次系数恰是经过 $t$ 个异常格的最短路径数。

当 $t\ge L$ 时，$f(t)=1$，这些次数只需知道系数总和。乘以 $x-1$ 后，高次系数之和等于原来的 $p_{L-1}$，故压缩转移没有丢失求期望所需的信息。最终按各次数的路径数乘对应电量并除以总路径数，得到的正是所求期望。

部分分算法

当 $n,m\le8$ 且 $k\le18$ 时，可以深度优先枚举所有向下或向右的最短路径，逐条模拟电量变化。

当 $k\le80$ 时，可以保存次数 $0$ 到 $k$ 的完整路径生成多项式。每对异常格的转移需要遍历全部次数，总复杂度为 $O(k^3+n+m)$。

复杂度分析

满分算法对每对异常格执行 $O(L)$ 次运算，其中 $L\le20$。时间复杂度为 $O(n+m+k^2\log s)$，空间复杂度为 $O(n+m+k\log s)$。