OJ Board

We are summing basically

seq * i^k

but for different ranges [a,b]. How to reduce this to run
in time? I cannot see how to precompute for this. Thanks!

Obviously, by computing partial sums.

For this problem, you just need to keep several arrays with partial sums, for each possible k.

How many arrays for each k?
2,3,4, or 5 ?

k<=20

One array for each k, i.e. 21 arrays in total.

I did the same thing. kept the partial sums of i^k S and
computed fF(k, a, b) using binomial expansion. Still I am getting WA?
it was running fine for sample inputs and all of my own testcases.

Could someone provide some inputs ?

It shouldn't be hard for you to write a brute-force program, and check your answers with it on random big cases.

And look out for overflows.

I understood how to deduce the answer from the partial sums when K = 1, but I failed to generalize it for K > 1.
How can the binomial expansion help me here?

Use binomial formula to expand (i-a+1)^k in terms of powers of i.

For K=2:
sum(seq * (i + (1-a))^2) =
sum(seq*i^2 + 2(1-a)*seq*i + (1-a)^2*seq) = sum(seq*i^2) + 2(1-a)*sum(seq*i) + (1-a)^2 * sum(seq).

Sums like sum(seq*i^2), sum(seq*i), etc can be done with a precomputation.