#P5158. 【模板】多项式快速插值

    ID: 4916 远端评测题 3000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数学O2优化快速傅里叶变换 FFT快速数论变换 NTT

【模板】多项式快速插值

题目背景

模板题,无背景

题目描述

给出 nn 个点 (xi,yi)(x_i, y_i)

求一个 n1n-1 次的多项式 f(x)f(x),使得 f(xi)yi(mod998244353)f(x_i)\equiv y_i\pmod{998244353}

输入格式

第一行输入一个正整数 nn

接下来 nn 行每行两个整数 xi,yix_i, y_i

输出格式

共一行,从低到高输出 f(x)f(x) 每一项的系数

若次数不够 n1n-1 次,用 00 补足

4
1 1
2 4
3 9
4 16
0 0 1 0

提示

1n1000001 \leqslant n \leqslant 100000

0xi,yi<9982443530 \leqslant x_i, y_i \lt 998244353

保证 xix_i 互不相同

对于 30%30\% 的数据,n5000n \leqslant 5000

注意,你输出的数必须是 [0,998244353)[0, 998244353) 范围内的整数

数据使用 CYaRon 在五分钟之内生成。