11444 - Sum

[zuluaga]

We are summing basically

seq[i] * 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!

[mf]

Obviously, by computing partial sums.

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

[zuluaga]

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

[emotional blind]

k<=20

[mf]

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

[pvncad]

I did the same thing. kept the partial sums of i^k S[i] 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 ?

[mf]

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.

[Khaled_912]

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?

[mf]

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

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

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