Read the official editorial first.

We need to find

\[\sum_{L+R=j-1} \binom{K-1}{L}\binom{N-K}{R}\min(L,R)\]

for all \(j=1,2,\dots,N\) in linear time.

After expanding, we get

\[\sum_{L,K-1-L,j-1-L,N-K-j+1+L\geq 0} \frac{(K-1)!(N-K)!\min(L,j-1-L)}{L!(K-1-L)!(j-1-L)!(N-K-j+1+L)!}\]

which is equal to

\[\frac{(K-1)!(N-K)!}{(j-1)!(N-j)!} \sum_{L} \binom{j-1}{L}\binom{N-j}{K-1-L}\min(L,j-1-L) \]

Consider an up-right lattice path \(p\) from \((0,0)\) to \((K-1,N-K)\). For \(0\leq i\leq N-1\), define \(p(i)=\min(x,y)\) where \((x,y)\) is the point where \(p\) reaches after \(i\) moves. Then the quantity \(\sum_L\binom{j-1}{L}\binom{N-j}{K-1-L}\min(L,j-1-L)\) is just the sum of \(p(j-1)\) for all possible paths \(p\) from \((0,0)\) to \((K-1,N-K)\)! Write it as \(f(j-1)\).

The rest of the solution is left as an exercise.

Hint: \(f(x)-f(x-1)\) for all \(x=1,2,\dots,N-1\) can be calculated in linear time using the trick similar to the following problem. https://atcoder.jp/contests/tenka1-2014-final-open/tasks/tenka1_2014_final_d