拉格朗日插值
\(n + 1\) 个点可以唯一确定一个最高为 \(n\) 次的多项式。
普通情况：
\(f(k) = \sum_{i = 1}^{n + 1} y_i \prod_{i \neq j} \frac{k - x[j]}{x[i] - x[j]}\)
例题：https://www.luogu.com.cn/problem/P4781
给定多项式上的 \(n\) 个点，求出 \(f(x)\)。
当横坐标是连续整数：
\(f(k) = \sum_{i = 1}^{n + 1} y_i \frac{\prod_{i \neq j} (k - j)}{(k - i)(-1)^{n + 1 - i}(i - 1)!(n + 1 - i)!}\)
例题：https://codeforc.es/problemset/problem/622/F
给定 \(n\) 和 \(k\)，求解 \(\sum_{i = 1}^{n} i^k\) 对 \(10^9 + 7\) 取模的值。
作者：Hamine
本文版权归作者和博客园共有，欢迎转载，但必须给出原文链接，并保留此段声明，否则保留追究法律责任的权利。