\(n\) 回以内にゴールする確率を求めるのではなく，\(P_n\) を直接的に求めることを考えます．

\(F(x)=\frac{x+\cdots+x^K}{K}\) とします．\(n\) 回サイコロを振ってマス \(i\) にいる確率は \([x^i]F(x)^n\) です．

ゴール直前にいるマスで場合分けして考えれば，次が成り立ちます．

\[\begin{aligned} P_n &=\sum_{i=1}^{K}\frac{K+1-i}{K}\times[x^{N-i}]F(x)^{n-1}\\ &=[x^N]\left(\sum_{i=1}^{K}\frac{K+1-i}{K}x^i\right)F(x)^{n-1}\\ &=[x^N]\left((K+1)F(x)-xF'(x)\right)F(x)^{n-1}\\ &=[x^N]\left((K+1)F(x)^n-xF'(x)F(x)^{n-1}\right) \end{aligned}\]

ここで

\[ [x^N]xF'(x)F(x)^{n-1} =\frac{1}{n}[x^N]x\left(F(x)^n\right)' =\frac{N}{n}[x^N]F(x)^n \]

が成り立つため，\(P_n=\left(K+1-\frac{N}{n}\right)[x^N]F(x)^n\) です．

公式解説 \(O(N\log N)\) 解法と同様に \(F(x)\) の逆関数を \(G(x)\) とすれば，ラグランジュ反転公式より

\[P_n=\left(K+1-\frac{N}{n}\right)\times\frac{n}{N}[x^{N-n}]\left(\frac{x}{G(x)}\right)^N\]

となり，公式解説における \(H(G(x))\) を計算するパートが不要になります．