Editorial for TLE '15 P5 - Prefix Sum Array
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