Consider a linear recurrence \(r\) where

• \(r_0\) is the initial term, and
• \(r_{n+1}=a\cdot r_n+b\) for \(n\in\{0, 1, \dots\}\).

If \(a=1\), \(r\) is an arithmetic sequence with the closed-form formula \(r_n = r_0+nb\).

If \(a\neq1\), the closed-form formula of \(r\) is given by

\[ \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} \]

using the fact that \(a^{n-1}b+a^{n-2}b+\dots+b\) is a geometric series.

The \(\text{dp}\) in the official editorial is a linear recurrence given by

• Initial term \(\text{dp}[0]=1\),
• Coefficient \(a=1-\frac{2(N-1)}{N^2}-\frac2{N^2}=1-\frac2N\lt1\), and
• Coefficient \(b=\frac2{N^2}\),

so its closed-form formula is

\[ \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} \]

Using the above formula, the solution to the original problem can be computed in \(O(\log K)\) time.