SUMSUMS - Summing Sums

no tags 

The N (1 ≤ N ≤ 50,000) cows, conveniently numbered 1, 2, ..., N, are trying to learn some encryption algorithms. After studying a few examples, they have decided to make one of their own! However, they are not very experienced at this, so their algorithm is very simple:

Each cow i is given a starting number Ci (0 ≤ Ci < 90,000,000), and then all the cows perform the following process in parallel:

  • First, each cow finds the sum of the numbers of the other N-1 cows.
  • After all cows are finished, each cow replaces her number with the sum she computed. To avoid very large numbers, the cows will keep track of their numbers modulo 98,765,431.

They told Canmuu the moose about it in November; he was quite impressed. Then one foggy Christmas Eve, Canmuu came to say:

"Your algorithm is too easy to break! You should repeat it T (1 ≤ T ≤ 1,414,213,562) times instead."

Obviously, the cows were very frustrated with having to perform so many repetitions of the same boring algorithm, so after many hours of arguing, Canmuu and the cows reached a compromise: You are to calculate the numbers after the encryption is performed!

Input

  • Line 1: Two space-separated integers: N and T.
  • Lines 2..N+1: Line i+1 contains a single integer: Ci.

Output

  • Lines 1..N: Line i contains a single integer representing the number of cow i (modulo 98,765,431) at the end of the encryption.

Example

Input:
3 4
1
0
4

Output:
26
25
29

The following is a table of the cows' numbers for each turn:

          Cows' numbers
Turn    Cow1  Cow2  Cow3
 0        1     0     4
 1        4     5     1
 2        6     5     9
 3       14    15    11
 4       26    25    29
Warning: large input/output data.

hide comments
smso: 2019-11-26 04:55:03

Use matrix exponentiation. There are only 2 distinct values (in the diagonal and off-diagonal respectively) in any intermediate step. Python3 is able to pass the grader.

rocky1729: 2019-11-15 11:22:39

@agarwal117
are u talking of iterative approach int which at every iteration each element is getting replaced by (sumofarray-prev. value at that element);
I think will cause overflow since the number of iters is very large (>10^8)

kesh4281: 2019-08-09 13:44:18

even if u get a wrong on test case #1, the program still runs until last case. So don't get confused that u r only getting WA in last case only.

agrawal117: 2019-08-01 16:33:22

very nice problem!!
its only a simple formula, not any matrix exponentiation,
all those who r getting wrong answer on TT 14 so may be they are applying matrix exp. or they r taking wrong mod
as when u have to subtract anything so it can be -ve also so always remember to add mod in last and again taking mod of that.

aayush_b1999: 2019-07-10 23:05:42

i wasn't doing modulus for sum of initial values.that's why i was getting wrong answer in test 14. so there might be problem with how you are doing mod. hope it helps other's problem.

Last edit: 2019-07-11 07:21:41
grucha78: 2019-06-02 16:51:15

Is it possible to get "Accepted" in Java? My program runs locally 0.03s for maximum set size, yet I get TLE.

infyy: 2018-06-01 10:15:44

Getting WA in last test case even though I have used 98765431

druh: 2017-12-01 14:24:58

WA on 14 :( Help PLEASE!

fresh: 2016-01-27 04:14:24

sorry for that
getting wrong answer you may probably derived the recurrence for some fixed n and that's wrong, the recurrence is related to n. also consider the case n = 1

fresh: 2016-01-26 14:49:21

there is something wrong with this problem
int main()
{
while(true);
}
the above code gets TLE on test 14 ! and it pass the previous ones

=(Francky)=> You have TLE for each test, and TLE is shown for the last one. Please do not post code here next time !

Last edit: 2016-01-26 16:29:49

Added by:Neal Wu
Date:2008-05-28
Time limit:0.160s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:USACO Chn 2007