UOJ Logo kczno1的博客

博客

【UER #6】逃跑的简单做法

2018-07-11 17:36:33 By kczno1

这是$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)$

代码http://uoj.ac/submission/265113

评论

jhr
你好像漏了一种啊 多算的情况还有,在经过$(a,b)$之前就没有经过$(a+x,b+y)$,但这不是第一次经过$(a+x,b+y)$ 还要再减去$\sum{j<i,a,b} h(j,x,y) \times g(i−j,0,0)$.

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。