SUMSUMS - Summing Sums

EntropyIncreaser 与 $T$ 次求和 **** ## 题目描述 $\mathsf E \color{red}\mathsf{ntropyIncreaser}$ 在BJOI2018上，秒切了一道链上二次求和，并吊打标算，觉得这是一道大水题。 然而 NaCly_Fish 表示很不服，她找了一道自己好久都没想出来的“ $T$次求和 ”给 $\mathsf E \color{red}\mathsf{ntropyIncreaser}$ 看。 给定一个长度为 $n$ 的序列 $a$，定义一次操作为： 将序列中的每个数变成除它外所有数的和。 求进行 $T$ 次操作之后的序列，答案对 $98765431$ 取模。 $\mathsf E \color{red}\mathsf{ntropyIncreaser}$ 瞟了一眼，说：“这题不是更水嘛。” 于是只用了 $\text{1ms}$ 写出AC代码，便大步走开。 机房里只剩下一脸懵逼的 NaCly_Fish，还不知道这题是怎么做的。 ## 输入输出格式 ### 输入格式 第一行两个正整数 $n,T$ 接下来 $n$ 行，每行一个整数 $a_i$，表示序列 $a$ 中的第 $i$ 个数。 ### 输出格式 输出 $n$ 行，每行一个整数，表示经过 $T$ 次操作后的序列，要对 $98765431$ 取模。 ## 说明 【样例解释】 $1$ ~ $4$ 次操作后的序列分别是： $$4,5,1$$ $$6,5,9$$ $$14,15,11$$ $$26,25,29$$ 【数据范围】 $1\le n \le 50000$ $0\le a_i \le9\times10^8$ $1\le T\le 1414213562$

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 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!

- Line 1: Two space-separated integers: N and T. - Lines 2..N+1: Line i+1 contains a single integer: C $ _{i} $ .

- 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.

3 4
1
0
4

26
25
29