# coreBugZJ

## EOJ 1851. Summing Sums 的三种巧妙解法

Summing Sums

Time Limit:1000MSMemory Limit:30000KB
Total Submit:408Accepted:86

Description

The N (1 <= N <= 50,000) cows, conveniently numbered 1..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 C_i (0 <= C_i < 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!

*Some extra feedback will be provided for the first 10 submissions to this problem.

Input

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

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.

Sample Input

3 4
1
0
4

INPUT DETAILS:
Three cows, with starting numbers 1, 0, and 4; four repetitions of the encryption algorithm.

Sample Output

26
25
29

OUTPUT DETAILS:
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
```

Source

usaco 07CHN

----------------------------------------------------------------------------------------

t = 0 时，
s[0] = cs = (n-1)^0 * cs
a[0][i] = c[i]

t = 1 时，
s[1] = (n-1)*s[0] = (n-1)^1  * cs
a[1][i] = s[0] – a[0][i] = (n-1)^0 * cs – c[i]

t = 2 时，
s[2] = (n-1)*s[1] = (n-1)^2  * cs
a[2][i] = s[1] – a[1][i] = ((n-1)^1-(n-1)^0)*cs + c[i]

t = 3 时，
s[3] = (n-1)*s[2] = (n-1)^3  * cs
a[3][i] = s[2] – a[2][i] = ((n-1)^2 – (n-1)^1 + (n-1)^0) * cs – c[i]

a[t][i] = [ (n-1)^(t-1) – (n-1)^(t-2) + (n-1)^(t-3) - … (n-1) ^ 0 ] * cs  +  (-1)^t * c[i]

----------------------------------------------------------------------------------------

----------------------------------------------------------------------------------------

A =

[ -1   1  ]
|         |
[ 0   n-1 ]

[ Ci ]          [ Ci ]
|    | = A^t  * |    |
[ CS ]          [ CS ]

posted on 2012-02-29 16:46 coreBugZJ 阅读(488) 评论(0)  编辑 收藏 引用 所属分类: ACMAlgorithm课内作业