Polynomial Construction

题目描述

已知一个素数 $p$ 和一个由 $p$ 个 0-1 整数组成的序列 $a_0, \ldots, a_{p-1}$。 求一个次数至多为 $p-1$ 的多项式 $f(x) = b_{p-1} x^{p-1} + b_{p-2} x^{p-2} + \ldots + b_0$，满足以下条件：

对于每个 $i$ $(0 \leq i \leq p-1)$，$b_i$ 是一个整数且满足 $0 \leq b_i \leq p-1$。 对于每个 $i$ $(0 \leq i \leq p-1)$，$f(i) \equiv a_i \pmod p$。

输入格式

输入按下列格式从标准输入给出： $p$ $a_0$ $a_1$ $\ldots$ $a_{p-1}$

输出格式

输出满足条件的多项式 $f(x)$ 的系数 $b_0, b_1, \ldots, b_{p-1}$，按此顺序并以空格分隔输出。 可以证明解总是存在。如果存在多个解，接受任意一个。

2
1 0

1 1

3
0 0 0

0 0 0

5
0 1 0 1 0

0 2 0 1 3

提示

$2 \leq p \leq 2999$ $p$ 是素数。 $0 \leq a_i \leq 1$$f(x) = x + 1$ 满足条件，如下所示：

$f(0) = 0 + 1 = 1 \equiv 1 \pmod 2$ $f(1) = 1 + 1 = 2 \equiv 0 \pmod 2$
$f(x) = 0$ 也是有效的。

标签: AtCoder|abc137F

来源

AtCoder|abc137F