#1919. [CTSC2010] 性能优化

[CTSC2010] 性能优化

题目描述

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

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)

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

输入格式

规范起见,以下将下标统一写到数组名称的右下角。例如:a1a_1 对应伪代码中的 a[1]xC0x_{C_0} 对应伪代码中的 x[C,0]

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

接下来一行包含 nn 个非负整数 a0,a1,,an1a_0, a_1, \cdots , a_{n - 1}

接下来一行包含 nn 个非负整数 b0,b1,,bn1b_0, b_1, \cdots , b_{n - 1}

输出格式

输出包含 nn 行,每行包含一个数。第 ii 行为 xC,imod(n+1)x_{C, i}\bmod (n + 1) 的值。你需要保证输出的数在 0n0 \sim n 之间。

4 1
1 2 3 4
4 3 3 1
2
1
0
2

说明/提示

总共 1010 个测试点,数据范围满足:

测试点 nn CC
1 100\le 100 100\le 100
2 109\le 10^9
3 700\le 700
4
5 104\le 10^4 =1= 1
6 105\le 10^5
7
8 5×105\le 5\times 10^5 109\le 10^9
9
10

在所有输入数据中,aia_ibib_i 均不超过 10910^9