拉格朗日插值

CSR：又拉又插的东西（又垃圾，又傻叉）

JCY：什么你拉插了一晚上？（我学习拉插学了一晚上）

什么是拉插

给定一些点值，是否可以求出一个函数，使得函数图像穿过这些点，并求出给定的 \(x\) 所对应的 \(y\)。

初步思路

前置

我们想到两个点肯定可以确定一条直线，而三个点肯定可以确定一条抛物线，所以我们猜测 \(n + 1\) 个点肯定可以确定一条 \(n\) 次的函数

正文：构造

考虑到我们可以强行让 \(x\) 取到某个值（比如 \(x_i\)）时，它所对应的值为 \(y_i\) 那么可以将式子变成 \(f(x)=y_ik\) 那么如何构造 \(k\) 便是我们要考虑的了，当 \(x\) 不取 \(x_i\)、在取其它 \(x_j\) 的时候，我们可以通过一个 \(x - x_j\) 来将其变为 \(0\)，可当 \(x_i\) 时，会有一些其他的东西混进去 (\(x-x_j\) 带来的) 所以我们在构造一个 \(a_i-a_j\) 就可以将前面带了的给去掉，考虑到上面是一个 \(0\) 就变成全 \(0\) 所以上面用乘法，所以将前面的去掉的部分我们也用乘法，两个部分一除，便是答案（哇，好抽象）：

\(f(x)=\sum y_i\prod\frac{x-x_i}{x_i-x_j}\)

我们也可以将其理解为构造出来一个 \(k\) 来将函数扭成平滑曲线（可以从分段函数，到用平滑曲线来链接）

CF622F The Sum of the k-th Powers

首先我们要证明 \(\sum i^k\) 是个 \(k + 1\) 次多项式，然后这里可以用 \(n^k-(n-1)^k\) 来证明差分后的次数会 \(-1\) 然后我们便可以证明上述命题（说了跟说了似的，算了自行推导），然后我们便可以考虑拉插，考虑到这些 \(x\) 值连续，所以我们便可以通过一些奇怪的做法将整个优化到 \(O(n)\)（哇，我真是个天才，这个也还不如自行推导）

#include <iostream>

using namespace std;
using ll = long long;

const int MaxN = 1e6 + 10, mod = 1e9 + 7;

ll f[MaxN], pr[MaxN], pl[MaxN], y[MaxN], n, k, ans, sum = 1;

ll qpow(ll a, ll b) {
  ll res = 1;
  for (ll i = 1; i <= b; i <<= 1) {
    (b & i) && (res = res * a % mod);
    a = a * a % mod;
  }
  return res;
}

int main() {
  cin >> n >> k, f[0] = pl[0] = pr[k + 3] = 1;
  for (int i = 1; i <= k + 2; i++) {
    f[i] = f[i - 1] * i % mod, sum = sum * (n - i) % mod;
    pl[i] = pl[i - 1] * (n - i) % mod;
  }
  for (int i = k + 2; i >= 1; i--) {
    pr[i] = pr[i + 1] * (n - i) % mod;
  }
  for (int i = 1; i <= k + 2; i++) {
    y[i] = (y[i - 1] + qpow(i, k)) % mod;
  }
  for (int i = 1; i <= k + 2; i++) {
    ll a = pl[i - 1] * pr[i + 1] % mod, b = f[i - 1] * f[k + 2 - i] % mod * ((k + 2 - i) % 2 ? -1 : 1) % mod;
    ans = (ans + a * qpow(b, mod - 2) % mod * y[i] % mod) % mod;
  }
  cout << (ans % mod + mod) % mod << endl;
  return 0;
}