以下の内容はhttps://kanpurin.hatenablog.com/entry/2021/06/22/164914より取得しました。

yukicoder No.612 Move on grid

ABC 典型解説競技プログラミング数え上げ形式的冪級数

形式的冪級数を用いた解法です．

問題はこちら

問題概要

${3}$ 次元グリッド上の ${(0,0,0)}$ からマンハッタン距離が ${1}$ の格子点に移動することを ${T}$ 回繰り返すしたあと ${(x,y,z)}$ にいるとして， ${d\leq ax+by+cz\leq e}$ となる確率に ${6^T}$ をかけた値を求めよ．各格子点への移動確率は ${\frac{1}{6}}$ であるとする．

${1\leq T\leq 500\\ |a|,|b|,|c|\leq 20\\ (a,b,c)\neq (0,0,0)\\ -10000\leq d\leq e\leq 10000}$

解説

問題は結局，最初 ${P=0}$ として， ${S=\{\pm a,\pm b,\pm c\}}$ のいずれかを ${P}$ に加算することを ${T}$ 回繰り返したとき ${d\leq P\leq e}$ になるような ${S}$ の要素の選び方の数が答えとなる．

${f=(x^a+x^{-a}+x^b+x^{-b}+x^c+x^{-c})^T}$ の ${x^d}$ から ${x^e}$ までの係数の和が答え．負の次数があるので非負の次数に変換する．

${M=\max(|a|,|b|,|c|)}$ として， ${f=(x^{M+a}+x^{M-a}+x^{M+b}+x^{M-b}+x^{M+c}+x^{M-c})^T}$ の ${x^{d+MT}}$ から ${x^{e+MT}}$ までの係数の和が答えとなる．ここで， ${P}$ は ${-MT}$ 未満になることはないので ${d\leftarrow\max(d,-MT)}$ としてよい．計算量は ${O(MT\log(MT))}$ ．定数倍重め．

提出プログラム

https://yukicoder.me/submissions/669021

感想

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

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