Luogu 4781 【模板】拉格朗日插值
2024-09-28 21:59:40
模板题。
拉格朗日插值的精髓在于这个公式
$$f(x) = \sum_{i = 1}^{n}y_i\prod _{j \neq i}\frac{x - x_i}{x_j - x_i}$$
其中$(x_i, y_i)$是给定的$n$个点值。
代入任何一个给定的点值坐标$x_k$,都会发现这个式子等于$y_k$成立,因为对于任何$i \neq k$,后面的系数都至少有一项为$0$,而当$i == k$的时候,后面那一项一定为$1$,这样子就可以保证代进去的点值一定被满足。
因为题目中要求直接代入$x$求值,所以在算这个式子的时候直接把$x$代进去计算就可以了,时间复杂度$O(n^2)$,要不然求系数的过程相当于高斯消元,时间复杂度$O(n^3)$。
Code:
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll; const int N = ;
const ll P = 998244353LL; int n;
ll k, xi[N], yi[N]; template <typename T>
inline void read(T &X) {
X = ; char ch = ; T op = ;
for (; ch > '' || ch < ''; ch = getchar())
if (ch == '-') op = -;
for (; ch >= '' && ch <= ''; ch = getchar())
X = (X << ) + (X << ) + ch - ;
X *= op;
} inline ll fpow(ll x, ll y) {
ll res = 1LL;
for (; y > ; y >>= ) {
if (y & ) res = res * x % P;
x = x * x % P;
}
return res;
} int main() {
read(n), read(k);
for (int i = ; i <= n; i++)
read(xi[i]), read(yi[i]); ll ans = 0LL;
for (int i = ; i <= n; i++) {
ll mul1 = 1LL, mul2 = 1LL;
for (int j = ; j <= n; j++) {
if (i == j) continue;
mul1 = mul1 * ((k - xi[j] + P) % P) % P;
mul2 = mul2 * ((xi[i] - xi[j] + P) % P) % P;
}
ans = (ans + yi[i] * mul1 % P * fpow(mul2, P - ) % P) % P;
} printf("%lld\n", ans);
return ;
}
最新文章
- PhpStorm 集成 开源中国(oschina.net)的Git项目,提交SVN时注意事项
- java integer对象判断两个数字是否相等
- 【转载】JMeter学习(一)工具简单介绍
- bootstrap学习笔记<;五>;(表单一)
- log4j的简单应用(转载)
- 富有魅力的git stash
- 检查string是否为double
- 校友信息管理&;SNS互动平台之技术框架选择
- POJ_1088 滑雪(记忆型DP+DFS)
- c++构造函数谁先执行的问题
- Ajax学习(三)——XMLHttpRequest对象的五步使使用方法
- Android 将Activity殴打jar包 对于由第三方使用 解决XML 图片 文本资源并不难过进入jar包装问题!
- windows7股票的,win8残疾人,安装Han澳大利亚sinoxn个时间,sinox它支持大多数windows软体
- Redis持久存储-AOF&RDB
- 想要薪资20-30K,Python程序员认真敲代码就够了!
- indexer_worker.go
- Linux lvs-NAT模式配置详解
- 《Effective C++》模板与泛型编程:条款32-条款40
- Python——编译标准
- 读zepto源码之工具函数