Power Sum — Solution & Editorial

Back to the Problem

∑ i^K is a polynomial of degree K+1 in N. Evaluate it at K+2 sample points (running prefix sums) and use Lagrange interpolation to get the value at N.

Complexity: O(K)

Watch out: A direct loop is O(N); the polynomial-interpolation trick is the intended O(K).