#abc137f. [abc137_f]Polynomial Construction

[abc137_f]Polynomial Construction

给出一个质数 pp 和长度为 nn 的数列 a0,,ap1a_0,\dots,a_{p-1},数列 aa 的每一项均为 0011

要求找到一个次数不超过 p1p-1 的多项式 bb,使得 f(x)=bp1xp1+bp2xp2++b0f(x)=b_{p-1}x^{p-1}+b_{p-2}x^{p-2}+\dots+b_0 满足以下条件:

  • 对于任意的正整数 ii0ip10 \le i \le p-1),0bip10 \le b_i \le p-1bib_i 为整数。

  • 对于任意的正整数 ii0ip10 \le i \le p-1),f(i)ai(modp)f(i) \equiv a_i \pmod p

保证 2p29992 \le p \le 2999。可以证明一定有解,输出任意一组解即可。