Editorial for TLE '15 P5 - Prefix Sum Array


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

For the 20% subtask, run the prefix sum array algorithm on the array M times.

In order to get 100% of the points, notice that if we try to solve this problem for a general array, the coefficients of the original array values produce a diagonal cut of Pascal's triangle. Thus, we need a fast way to generate combinations.

The combinations needed are:

\displaystyle \binom{M}{0}, \binom{M+1}{1}, \binom{M+2}{2}, \binom{M+3}{3}, \binom{M+4}{4}, \dots, \binom{M+N-1}{N-1}

The first coefficient is always 1 (since \dbinom{M}{0} = 1). Then, by using the formula given in P4, coeff[i] = \dfrac{coeff[i-1] \times (M+i)}{i}. The last challenge is to divide by i; we must instead multiply by the inverse of i. The inverse of i is some other integer j such that (i \times j) \equiv 1 \pmod{10^9+7}. The reason is that (A \times i \times B) \times j \equiv (A \times B) \times (i \times j) \equiv A \times B \pmod{10^9+7} which gets rid of the number i; this has the same effect as division.

From Fermat's Little Theorem, a^{p-1} \equiv 1 \pmod p if p is prime. Since 10^9+7 is prime, we can see that i \times i^{10^9+7-2} \equiv 1. Thus, the inverse of i is i^{10^9+5}. Again, the quick power algorithm must be used.

After generating the first N coefficients, the rest of the problem should be trivial to solve.

Time complexity: \mathcal{O}(N^2)

Bonus: Given M and the output array, can you quickly find the input array?


Comments