初項が \(r_0\) であって、\(n\in\{0, 1, \dots\}\) について \(r_{n+1}=a\cdot r_n+b\) で与えられる線形漸化式 \(r\) を考えます。

\(a=1\) ならば \(r\) は等差数列です。この場合、\(r\) の一般項は \(r_n = r_0+nb\) です。

\(a\neq1\) の場合、等比級数の公式を用いると、\(r\) の一般項は

\[ \begin{aligned} r_n&=ar_{n-1}+b\\ &=a(ar_{n-2}+b)+b\\ &\enspace\vdots\\ &=\underbrace{a(a(\dots(a}_{n\text{ }a\text{'s}}r_0+\underbrace{b)+\dots)+b)+b}_{n\text{ }b\text{'s}}\\ &=a^nr_0+a^{n-1}b+a^{n-2}b+\dots+b\\ &=a^nr_0+\left(\frac{a^n-1}{a-1}\right)b\\ &=a^n\left(r_0+\frac{b}{a-1}\right)-\frac{b}{a-1} \end{aligned} \]

と表せます。

公式解説における \(\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)\) 時間で計算できます。