题目大意:给你$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;
}

  

最新文章

  1. 移除HTML5 input在type=&quot;number&quot;时的上下小箭头
  2. 数组去重及数组的prototype原型
  3. Linux练习
  4. png,jpg,gif格式的图片的选择
  5. 编译生成.NET Core Framework遇到的问题
  6. 《SQL Server企业级平台管理实践》读书笔记——SQL Server中关于系统库Tempdb总结
  7. onSaveInstanceState(Bundle outState)的调用时机
  8. EF Code First:实体映射,数据迁移,重构(1)
  9. Cloud Insight 现在已经支持监控 Cassandra 啦!
  10. Identity Card(水题)
  11. Android:ListViewAdapter
  12. 【C语言的日常实践(十二)】命令行参数
  13. “玲珑杯”ACM比赛 Round #22 E 贪心,脑洞
  14. spring事务学习笔记
  15. WPF:完美自定义MeaagseBox 动画 反弹 背景模糊 扁平化
  16. Maven的pom配置文件
  17. 【hihoCoder】#1133 : 二分&#183;二分查找之k小数
  18. Fastjson 爆出远程代码执行高危漏洞,更新版本已修复
  19. InstallShield2015创建安装包
  20. HDS推出HUS中端阵列 文件、块和对象统一存储

热门文章

  1. P1209 [USACO1.3]修理牛棚 Barn Repair
  2. CLR via c#读书笔记九:接口
  3. libevent学习六(Connect listeners )
  4. uvaoj 10474 - Where is the Marble?(sort+lower_bound)
  5. POSTMan 快速上手(一图带你玩 Postman )
  6. 第三模块:面向对象&amp;网络编程基础 第1章 面向对象
  7. org.apache.spark.launcher.Main源码分析
  8. 使用open live writee写的博客
  9. 关于C#中如何使用wmi获得操作系统信息?
  10. 条款02:尽量以const,enum,inline替换#define