#P13614. [ABC137F] Polynomial Construction

    ID: 12814 传统题 1000ms 256MiB 尝试: 4 已通过: 2 难度: 6 上传者: 标签>CF2000提高费马小定理Lagrange 插值同余的加减乘运算

[ABC137F] Polynomial Construction

题目描述

给定一个素数 pp,以及一个长度为 pp 的只包含 00 和 11 的整数序列 a0, a1, …, ap−1a_0,\ a_1,\ \ldots,\ a_{p-1}。

请你求出一个满足以下条件的次数不超过 p−1p-1 的多项式 $f(x) = b_{p-1} x^{p-1} + b_{p-2} x^{p-2} + \ldots + b_0$。

  • 对于每个 ii(0≤i≤p−10 \leq i \leq p-1),bib_i 是满足 0≤bi≤p−10 \leq b_i \leq p-1 的整数。
  • 对于每个 ii(0≤i≤p−10 \leq i \leq p-1),有 f(i)≡ai(modp)f(i) \equiv a_i \pmod{p}。

输入格式

输入通过标准输入给出,格式如下:

pp a0a_0 a1a_1 …\ldots ap−1a_{p-1}

输出格式

请输出满足条件的多项式 f(x)f(x) 的一组 b0, b1, …, bp−1b_0,\ b_1,\ \ldots,\ b_{p-1} 的值,按顺序用空格分隔。

保证一定存在解。如果有多组解,输出其中任意一组均可。

输入输出样例 #1

输入 #1

2
1 0

输出 #1

1 1

输入输出样例 #2

输入 #2

3
0 0 0

输出 #2

0 0 0

输入输出样例 #3

输入 #3

5
0 1 0 1 0

输出 #3

0 2 0 1 3

说明/提示

限制

  • 2≤p≤29992 \leq p \leq 2999
  • pp 是素数。
  • 0≤ai≤10 \leq a_i \leq 1

样例解释 1

f(x)=x+1f(x) = x + 1 满足条件。

  • f(0)=0+1=1≡1(mod2)f(0) = 0 + 1 = 1 \equiv 1 \pmod{2}
  • f(1)=1+1=2≡0(mod2)f(1) = 1 + 1 = 2 \equiv 0 \pmod{2}

样例解释 2

f(x)=0f(x) = 0 也是一个有效输出。