初項が \(r_0\) であって、\(r_{n+1}=a\cdot r_n+b \, (n\in\{0, 1, \dots\})\) で定まる線形漸化式 \(r\) について、\(a\neq1\) ならば \(r\) の一般項は

\[r_n=a^n\left(r_0+\frac{b}{a-1}\right)-\frac{b}{a-1}\]

で与えられます。

公式解説における漸化式 \(\text{dp}\) は

• 初項 \(\text{dp}[0]=1\)
• 係数 \(a=1-\frac{2(N-1)}{N^2}-\frac2{N^2}=1-\frac2N\lt1\)
• 係数 \(b=\frac2{N^2}\)

であることから、その一般項は

\[ \begin{aligned} \text{dp}[i]&=\left(1-\frac2N\right)^i\left(1+\frac{2/N^2}{-2/N}\right)-\frac{2/N^2}{-2/N} \\ &=\left(1-\frac2N\right)^i\left(1-\frac1N\right)+\frac1N \end{aligned} \]

となります。以上の式を用いることで、元の問題の解を \(O(\log K)\) 時間で計算できます。