Warning: session_start(): open(/tmp/sess_4efdfb1df436a6ccf581a5d52542450b, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 拉格朗日插值法 ======
===== 作用 =====
如果发现某个数学题，答案有可能是多项式的结构的话
然后又恰好打出了表
不如直接插值。也省的推公式了（其实是推不出来
===== Code =====
int lagrange(int *X, int *Y, ll n, ll k) {
ll res = 0, l;
for(int i = 0;i < n; ++i) {
l = 1;
for(int j = 0;j < n; ++j) {
if(i == j) continue;
l = l * Sub(k, X[j]) % mod;
l = l * Get_Inv(Sub(X[i], X[j])) % mod;
}
res = (res + l * Y[i] % mod) % mod;
}
return res;
}
===== 题目 =====
[[https://atcoder.jp/contests/aising2020/tasks/aising2020_f|Alsing Programming Contest 2020 F]]