TLE '15 P5 - Prefix Sum Array - DMOJ: Modern Online Judge

TLE '15 P5 - Prefix Sum Array

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 256M

Authors:

Problem type

Fax McClad, Croneria's most courageous bounty hunter, often has weird dreams in his sleep. Sometimes, he dreams about his past experiences, and at other times, he has nightmares about problem statements that have no relation to the actual problem.

One night, Fax had a very, very bizarre dream about d:

d received an array of length $N$ $N$ $(1 \le N \le 2\,000)$ $(1 \leq N \leq 2 000)$ with elements numbered from $1 \dots N$ $1 \dots N$ , and he performed the sum operation on it.

The sum operation takes in an array $A$ $A$ and returns an array $B$ $B$ . Array $B$ $B$ has these two important properties:

Array $A$ $A$ and array $B$ $B$ are equal in length.

For all elements $B_k$ $B_{k}$ , the element satisfies $B_k = A_1+A_2+\dots+A_k$ $B_{k} = A_{1} + A_{2} + \dots + A_{k}$ .

Unimpressed with the result, d fed the result back in to the sum operation repeatedly, performing the operation $M$ $M$ $(2 \le M \le 10^9)$ $(2 \leq M \leq 10^{9})$ times in total. At this point, d

Suddenly, Fax wakes up! Disturbed by the abstract dream, he asks you to help solve the problem so he can focus on his bounty hunting.

Constraints

Subtask 1 [20%]

$N \times M \le 10^6$ $N \times M \leq 10^{6}$

Subtask 2 [60%]

$N \le 100$ $N \leq 100$

Subtask 3 [20%]

No additional constraints.

Input Specification

The first line will contain $N$ $N$ , the number of elements in the array.

The next line will contain the elements $A_1, A_2, \dots, A_N$ $A_{1}, A_{2}, \dots, A_{N}$ $(0 \le A_i \le 10^9+6)$ $(0 \leq A_{i} \leq 10^{9} + 6)$ , each separated by a space.

The final line of input will contain $M$ $M$ , the number of times the sum operation is performed.

Output Specification

The array after performing $M$ $M$ sum operations on the given array.

Each element should be outputted mod $10^9+7$ $10^{9} + 7$ and elements should be separated by a single space.

Sample Input

Copy

5
4 2 8 1 1
2

Sample Output

Copy

4 10 24 39 55

Explanation for Sample Output

After one sum operation, the array is changed to:

Copy

4 6 14 15 16

After the second sum operation, the array is changed to:

Copy

4 10 24 39 55

Comments

2

LeonLiur commented on Feb. 11, 2022, 2:20 a.m.

this problem is so so so good.. hands down one of the best

7

septence123 commented on Feb. 25, 2017, 2:54 a.m. ← edited →

So I submitted in pypy and got everything correct except for the last test case of the last batch is there any further optimizations i can implement?

0

mrmackamoo commented on March 24, 2020, 7:03 p.m.

same