P4191 [CTSC2010] Performance Optimization

# Description Programmer Xiao Ming is developing a large software system. There is a core routine described by the following pseudocode (assume all variables are initially $0$, and that none of the data types will overflow): ~~~cpp Input a[0], a[1], ... , a[n - 1], b[0], b[1], ... , b[n - 1], C For i: 0 to n - 1 x[0, i] = a[i] For i: 0 to C - 1 For j: 0 to n - 1 For k: 0 to n - 1 x[i + 1, (j + k) mod n] = x[i + 1, (j + k) mod n] + b[k]x[i, j] Output x[C, 0] mod (n + 1), x[C, 1] mod (n + 1), ... , x[C, n - 1] mod (n + 1) ~~~ However, this program is very inefficient; its time complexity is $\Theta(n^2 C)$. He wants you to optimize this program while producing the same output. To make the problem easier, he guarantees that the input $n$ can be written as a product of some positive integers, each no greater than $10$, and that $n + 1$ is prime.

程序员小明正在开发一套大型软件，软件中有一段核心程序，用伪代码描述如下（假设所有变量初值均为 $0$，并且假定其中的数据类型均不会出现溢出）： ~~~cpp Input a[0], a[1], ... , a[n - 1], b[0], b[1], ... , b[n - 1], C For i: 0 to n - 1 x[0, i] = a[i] For i: 0 to C - 1 For j: 0 to n - 1 For k: 0 to n - 1 x[i + 1, (j + k) mod n] = x[i + 1, (j + k) mod n] + b[k]x[i, j] Output x[C, 0] mod (n + 1), x[C, 1] mod (n + 1), ... , x[C, n - 1] mod (n + 1) ~~~ 但是，这段程序的效率非常低，它的时间复杂度高达 $\Theta(n^2C)$。他想让你帮忙优化一下这个程序，当然要求输出相同的结果。为了使问题更简单，他保证输入的 $n$ 能表示成若干个不超过 $10$ 的正整数的乘积，并且 $n + 1$ 是质数。

规范起见，以下将下标统一写到数组名称的右下角。例如： $a_1$ 对应伪代码中的 `a[1]`，$x_{C, 0}$ 对应伪代码中的 `x[C, 0]`。 输入的第一行包含两个非负整数 $n, C$。 接下来一行包含 $n$ 个非负整数 $a_0, a_1, \cdots , a_{n - 1}$。 接下来一行包含 $n$ 个非负整数 $b_0, b_1, \cdots , b_{n - 1}$。

Output contains $n$ lines, one number per line. The $i$-th line is the value of $x_{C, i} \bmod (n + 1)$. You should ensure each printed number is between $0$ and $n$ inclusive.

There are $10$ test points in total. Constraints: | Test Point | $n$ | $C$ | | :--------: | :------------------: | :---------: | | 1 | $\leq 100$ | $\leq 100$ | | 2 | $\leq 100$ | $\leq 10^9$ | | 3 | $\leq 700$ | $\leq 10^9$ | | 4 | $\leq 700$ | $\leq 10^9$ | | 5 | $\leq 10^4$ | $ = 1$ | | 6 | $\leq 10^5$ | $= 1$ | | 7 | $\leq 10^5$ | $= 1$ | | 8 | $\leq 5 \times 10^5$ | $\leq 10^9$ | | 9 | $\leq 5 \times 10^5$ | $\leq 10^9$ | | 10 | $\leq 5 \times 10^5$ | $\leq 10^9$ | In all testdata, $a_i$ and $b_i$ do not exceed $10^9$. Translated by ChatGPT 5