## Editorial for TLE '15 P5 - Prefix Sum Array

**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 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:

The first coefficient is always (since ). Then, by using the formula given in P4, . The last challenge is to divide by ; we must instead multiply by the inverse of . The inverse of is some other integer such that . The reason is that which gets rid of the number ; this has the same effect as division.

From Fermat's Little Theorem, if is prime. Since is prime, we can see that . Thus, the inverse of is . Again, the quick power algorithm must be used.

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

Time complexity:

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

## Comments

Similar problem: https://codeforces.com/contest/1967/problem/C