以下の内容はhttps://kanpurin.hatenablog.com/entry/2022/07/16/144159より取得しました。

yukicoder No.2013 Can we meet?

yukicoder 形式的冪級数式変形期待値競技プログラミング解説

ほとんど公式解説と同じなので簡単に書きます。

問題はこちら

問題概要

2点 ${(x_1,y_1),(x_2,y_2)}$ がそれぞれ上下左右に ${1}$ 移動することを ${N}$ 回繰り返す．移動は左右には ${\frac{A}{2(A+B)}}$ の確率で，上下には ${\frac{B}{2(A+B)}}$ の確率で移動するとき、2点が ${i}$ 回目の移動直後に初めて重なる確率を ${p_i}$ としたときの ${\sum_{i=1}^{N}p_i×a_i}$ を求めよ．

${1\leq N\leq 10^5}$
${0\leq x_1,y_1,x_2,y_2\leq 10^9}$
${(x_1,y_1)\neq (x_2,y_2)}$
${1\leq A,B\leq 10^6}$
${1\leq a_i\leq 10^9}$

解説

公式解説と同様に ${x=|x_1-x_2|,y=|y_1-y_2|}$ とします．以降， ${2N}$ 回の移動で ${(0,0)}$ から ${(x,y)}$ への移動を考ます．
ここで，

${f(n):=(0,0)}$ から ${2n}$ 回の移動後に初めて ${(x,y)}$ にいる確率
${g(n):=(0,0)}$ から ${2n}$ 回の移動後に ${(x,y)}$ にいる確率
${h(n):=(0,0)}$ から ${2n}$ 回の移動後に ${(0,0)}$ にいる確率

とすると， ${g(n)=\sum_{i=0}^{n}f(i)×h(n-i)}$ が成り立ちます．公式解説と同様の方法で ${g,h}$ を計算した後， ${f,g,h}$ を形式的冪級数と考えると ${f=g/h}$ として ${f}$ を求めることができます．

計算量は ${O(N\log{N})}$ です．

提出プログラム

https://yukicoder.me/submissions/779185

感想

結構きれいな形になった．

以上の内容はhttps://kanpurin.hatenablog.com/entry/2022/07/16/144159より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます

不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14