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\neq1\), the closed-form formula of \(r\) is given by

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

The recurrence relation \(\text{dp}\) in the official editorial is 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.