| 题目名称 | 2784. 多项式插值Ⅱ |
|---|---|
| 输入输出 | interpolation2.in/out |
| 难度等级 | ★★★★☆ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 FoolMike
于2017-08-21加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：10， 提交：37， 通过率：27.03% | ||||
 FoolMike |
100 | 5.406 s | 8.88 MiB | C++ |
 131441373 |
100 | 6.180 s | 42.79 MiB | C++ |
 unknown |
100 | 6.304 s | 50.11 MiB | C++ |
 sshockwave |
100 | 7.850 s | 44.06 MiB | C++ |
|
sshockwave |
100 | 7.917 s | 44.06 MiB | C++ |
 Owen |
100 | 9.164 s | 11.56 MiB | C++ |
 i207M |
100 | 9.360 s | 174.37 MiB | C++ |
|
Owen |
100 | 9.511 s | 14.41 MiB | C++ |
|
Owen |
100 | 9.532 s | 14.41 MiB | C++ |
|
Owen |
100 | 9.568 s | 11.56 MiB | C++ |
| 关于 多项式插值Ⅱ 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
不会n
 发光二向箔
2019-11-04 22:17
4楼
| ||||
|
新人求助，刚学c++(
本机0.7提交2.0+ QwQ unknown
2018-11-28 16:26
3楼
| ||||
|
不卡常才三个人过，怕不是有毒
 Rockdu
2018-07-28 22:34
2楼
| ||||
|
尴尬的是log^2的更好写，而且不用做太多常数优化，只需要改进一下多点求值算法的常数就很优秀了！
| ||||
【题目描述】
给出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
【数据范围】
对于所有数据，n<=20000
【来源】
被自己打脸的Mike……
UPD:学会O(n(logn)^2)后又打脸，这次我开了std用时的1.5倍还多的时间，绝不卡常！