AdditionalFile5079.zip

#5079. 「POI2018 R3」多项式 Polynomial

标签: 传统 | 时间限制: 15000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXV Olimpiada Informatyczna — III etap Wielomian

Bajtazar 在数学课上行为不端，作为惩罚，他需计算一个具有 $n$ 个整数系数的长多项式 $W$：

$$W(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_{n-2} x^{n-2} + a_{n-1} x^{n-1}$$

在点 $q^1, q^2, \ldots, q^n$ 处的取值。为便于老师检查，他需先给出这些取值之和除以 $m$ 的余数，再给出各取值除以 $m$ 的余数。

Bajtazar 不仅调皮，还很懒惰，他请你帮忙，自己却跑去派对了。临走前，他提醒你：$n$ 是 $2$ 的幂，且 $q^n$ 除以 $m$ 的余数为 $1$（即 $q^n \bmod m = 1$）。他认为这些性质可大幅减少计算量。

输入格式

第一行包含三个整数 $n, m, q$（$n \geq 1$，$n$ 为 $2$ 的幂，$2 \leq m \leq 10^9$，$1 \leq q < m$，$q^n \bmod m = 1$）。

第二行包含 $n$ 个整数 $a_0, a_1, \ldots, a_{n-1}$ $(0 \leq a_i \leq 10^9)$，表示多项式系数。

输出格式

第一行输出一个整数，表示多项式 $W$ 在点 $q^1, q^2, \ldots, q^n$ 的取值之和除以 $m$ 的余数。

第二行输出 $n$ 个整数，表示 $W(q^1), W(q^2), \ldots, W(q^n)$ 除以 $m$ 的余数，空格分隔。

样例

输入

4 13 5
3 2 2 1

输出

12
6 2 9 8

多项式为 $W(x) = 3 + 2x + 2x^2 + x^3$，其在各点取值为 $W(5) = 188$，$W(5^2) = 16928$，$W(5^3) = 1984628$，$W(5^4) = 244923128$。第一行输出 $188 + 16928 + 1984628 + 244923128 = 246924872$ 除以 $13$ 的余数，即 $12$。第二行输出各取值除以 $13$ 的余数：$188 \bmod 13 = 6$，$16928 \bmod 13 = 2$，$1984628 \bmod 13 = 9$，$244923128 \bmod 13 = 8$。

附加样例

1. $n=8, m=10, q=3$。
2. $n=256, m=10, q=9$。
3. $n=2^{13}, m=17, q=6$。
4. $n=2^{20}, m=1114129, q=2$。

数据范围与提示

若和正确但某取值错误，程序可获得 $40\%$ 的分数，且第二行需输出 $n$ 个 $[0, m-1]$ 范围的数。

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$n \leq 2^{10}$	$17$
$2$	$n \leq 2^{15}$	$9$
$3$	$n \leq 2^{20}$	$74$