2782. 多项式插值

【题目描述】

给出n个点(xi,yi)，满足对于任意的i,j满足1<=i,j<=n,当xi=xj时必有yi=yj。求出一个次数不超过n-1的多项式，使得对于任意的i满足1<=i<=n，有f(xi)=yi。现在请你求出多项式f(x)。

为了防止精度误差，本题在模998244353意义下求解(=119<<23|1，是一个质数，原根是3)

【输入格式】

第一行一个整数n。

接下来n行，每行两个整数xi,yi。数据保证0<=xi,yi<998244353

【输出格式】

一行n个整数，分别对应多项式f(x)中x^0到x^(n-1)的系数。

【样例输入】

4
1 1
2 5
3 14
4 30

【样例输出】

0 166374059 499122177 332748118  

【数据范围】

对于50%的数据，n<=500

对于100%的数据，n<=5000

【提示】

又是垃圾Mike出的多项式题。

我猜快速插值跑不过牛顿插值……求神犇光速打脸，我用的是牛顿插值。

upd:被自己O(n(logn)^3)的垃圾插值打脸了……