かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

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

感想