这是$jhr$优化得到的.
首先把求方差转化为求$E(x)$和$E(x^2)$($x$表示某个方案经过的不同位置数,$E$表示期望)
定义$f(i,x,y)$表示第$i$天第一次到达$(x,y)$的概率,$g(i,x,y)$表示第$i$天到达$(x,y)$的概率.
$g$很好算,$f$用$g$容斥一下就可以算了.
$E(x)$只用对$f$求和就好了.
$x^2=2{x \choose 2}+x$,所以$E(x^2)$转化为求$E({x \choose 2})$,然后就转化为$\sum_{x,y} x,y$都被经过的概率.
定义$h(i,x,y)$表示第$i$天第一次到达了一个点$(a,b)$,且之前经过了$(a-x,b-y)$的所有情况的概率和.
答案就是对$h$求和.
怎么计算$h(i,x,y)$呢?
先考虑$\sum_{j < i,a,b} f(j,a,b) \times f(i-j,x,y)$
它多算的情况就是,在经过$(a,b)$之前就已经经过了$(a+x,b+y)$
再减去$\sum_{j < i} h(j,-x,-y) \times f(i-j,x,y)$就好了.
时间$O(n^4)$
鄂公网安备 42010202000505 号