Comet OJ

C0454 [CTSC2010Day1-C]性能优化

内存限制：256 MB 时间限制：6000 ms

题目描述

程序员小明正在开发一套大型软件，软件中有一段核心程序，用伪代码描述如下（假设所有变量初值均为 0，并且假定其中的数据类型均不会出现溢出）：

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)

但是，这段程序的效率非常低，它的时间复杂度高达 $Θ(n^2C)$。他想让你帮忙优化一下这个程序，当然要求输出相同的结果。为了使问题更简单，他保证输入的 $n$ 能表示成若干个不超过 $10$ 的正整数的乘积，并且 $n+1$ 是质数。

输入格式

规范起见，以下将下标统一写到数组名称的右下角。例如：$a_1$​ 对应伪代码中的a[1]，$x_{C,0}$​ 对应伪代码中的x[C, 0]。

输入的第一行包含两个非负整数 $n,C$。

接下来一行包含 $n$ 个非负整数 $a_0,a_1,⋯,a_{n−1}$​。

接下来一行包含 $n$ 个非负整数 $b_0,b_1,⋯,b_{n−1}$​。

输出

输出包含 $n$ 行，每行包含一个数。第 $i$ 行为 $x_{C,i}\mod(n+1)$ 的值。你需要保证输出的数在 $0∼n$ 之间。

样例

样例输入 1

4 1
1 2 3 4
4 3 3 1

样例输出 1

2
1
0
2

提示

总共10个测试点，数据范围满足：

测试点1：$n≤100,C≤100$
测试点2：$n≤100,C≤10^9$
测试点3：$n≤700,C≤10^9$
测试点4：$n≤700,C≤10^9$
测试点5：$n≤10^4,C=1$
测试点6：$n≤10^5,C=1$
测试点7：$n≤10^5,C=1$
测试点8：$n≤5 \times 10^5,C≤10^9$
测试点9：$n≤5 \times10^5,C≤10^9$
测试点10：$n≤5 \times10^5,C≤10^9$

在所有输入数据中，$a_i$​ 和 $b_i$​ 均不超过 $10^9$。