UER 6 逃跑

模拟赛题

一句话题意：二维平面带权随机游走经过不同位置的方差

设 $w=\sum w_i$

因为 $\mathrm{Var}(X)=E(X^2)-E(X)^2$

所以我们仅需要求出来 $X^2$ 和 $X$ 的期望

$X$ 的期望我们可以考虑每个点的贡献，我们希望统计出经过某一个点然后再也不经过的方案数

设 $W(i,x,y)$ 为行走了 $i$ 步最终到 $(x,y)$ 的带权方案数，可以简单递推

$g_i$ 表示走了 $i$ 步且不经过 $(0,0)$ 的方案数

有 $E(X) =\sum\limits_{i}^{n}\sum\limits_{(x,y)}W(i,x,y)g_{n-i}$

也就是走到了 $(x,y)$ 并且剩下的步数不返回来

$E(X^2)$ 并不好直接统计，考虑 $x^2 = 2\binom{x}{2} +x$

前一部分是所有有序的相互到达点对的数量，后面就是 $X$

那么设 $R(i,x,y)$ 表示走了 $i$ 步，到了 $(x,y)$ 不经过 $0$ 点的方案数

$S(i,x,y)$ 表示走了 $i$ 步，回到 $(0,0)$ 且中间经过了 $(x,y)$ 的方案数

有 $R(i,x,y) = W(i,x,y) - \sum\limits_{j=1}^{i}W(j,0,0)R(i-j,x,y)$

$S(i,x,y) = \sum\limits_{j=1}^{i}W(j,x,y)R(i-j,-x,-y)$

都比较显然

那么设 $F(i,x,y)$ 表示走了 $i$ 步，存在一个 $(a,b)$ 为第一次到达且最终第一次到达 $(a+x,b+y)$

这样 $E(\binom{x}{2})=\sum\limits_{i=0}^{n}\sum\limits_{(a,b)\neq(0,0)}F(i,a,b)w^{n-i}$

这是所有有序对的个数

考虑求 $F(i,x,y)$

一开始有 $F(i,x,y) = \sum\limits_{j=0}^{i-1}g_jW(i-j,x,y)$

考虑减去不合法的方案数

先减去 $(a+x,b+y) \to (a,b) \to (a+x,b+y)$ 的方案数

$F(i,x,y) \gets F(i,x,y)-\sum\limits_{j=0}^{i-1}g_jS(i-j,-x,-y)$

然后要减去 $(a,b) \to (a+x,b+y) \to (a,b) \to (a+x,b+y)$ 的方案

即 $\sum\limits_{j=0}^{i-1}F(j,x,y)W(i-j,0,0)$

不过第一步容斥已经减掉了一部分，要加回来，所以

$F(i,x,y) \gets F(i,x,y) - \sum\limits_{j=0}^{i-1}F(j,x,y)(W(i-j,0,0)-S(i-j,-x,-y))$

$O(n^4)$