[洛谷P4781]【模板】拉格朗日插值
2024-10-16 02:28:32
题目大意:给你$n(n\leqslant2000)$个点,要你求$n-1$次经过这$n$个点的多项式在$k$处的值
题解:$Lagrange$插值:
$$
f_x=\sum\limits_{i=1}^ky_i\prod\limits_{j=1,j\not=i}^k\dfrac{x-x_j}{x_i-x_j}
$$
卡点:无
C++ Code:
#include <algorithm>
#include <cstdio>
#define maxn 2010
const int mod = 998244353;
namespace Math {
inline int pw(int base, int p) {
static int res;
for (res = 1; p; p >>= 1, base = static_cast<long long> (base) * base % mod) if (p & 1) res = static_cast<long long> (res) * base % mod;
return res;
}
inline int inv(int x) { return pw(x, mod - 2); }
}
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int getreduce(int x) { return x + (x >> 31 & mod); } int n, k, ans;
int x[maxn], y[maxn];
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i) scanf("%d%d", x + i, y + i);
for (int i = 1; i <= n; ++i) {
long long a = y[i], b = 1;
for (int j = 1; j <= n; ++j) if (i != j) {
a = a * getreduce(k - x[j]) % mod;
b = b * getreduce(x[i] - x[j]) % mod;
}
reduce(ans += a * Math::inv(b) % mod - mod);
}
printf("%d\n", ans);
return 0;
}
最新文章
- 移除HTML5 input在type=";number";时的上下小箭头
- 数组去重及数组的prototype原型
- Linux练习
- png,jpg,gif格式的图片的选择
- 编译生成.NET Core Framework遇到的问题
- 《SQL Server企业级平台管理实践》读书笔记——SQL Server中关于系统库Tempdb总结
- onSaveInstanceState(Bundle outState)的调用时机
- EF Code First:实体映射,数据迁移,重构(1)
- Cloud Insight 现在已经支持监控 Cassandra 啦!
- Identity Card(水题)
- Android:ListViewAdapter
- 【C语言的日常实践(十二)】命令行参数
- “玲珑杯”ACM比赛 Round #22 E 	贪心,脑洞
- spring事务学习笔记
- WPF:完美自定义MeaagseBox 动画 反弹 背景模糊 扁平化
- Maven的pom配置文件
- 【hihoCoder】#1133 : 二分&#183;二分查找之k小数
- Fastjson 爆出远程代码执行高危漏洞,更新版本已修复
- InstallShield2015创建安装包
- HDS推出HUS中端阵列 文件、块和对象统一存储
热门文章
- P1209 [USACO1.3]修理牛棚 Barn Repair
- CLR via c#读书笔记九:接口
- libevent学习六(Connect listeners )
- uvaoj 10474 - Where is the Marble?(sort+lower_bound)
- POSTMan 快速上手(一图带你玩 Postman )
- 第三模块:面向对象&;网络编程基础 第1章 面向对象
- org.apache.spark.launcher.Main源码分析
- 使用open live writee写的博客
- 关于C#中如何使用wmi获得操作系统信息?
- 条款02:尽量以const,enum,inline替换#define