知识点: 拉格朗日插值

原题面


题意简述

定义前 $n$ 个自然数 $k$ 次幂的和为:

$$S_k(n) = \sum_{i=1}^{n}i^k$$

给定 $n,k$,求 $S_k(n)$。
$1\le n\le 10^9,\ 1\le k\le 10^6$。


分析题意

一个性质

$S_k(n)$ 为关于 $n$ 的 $k+1$ 次多项式。

证明考虑对 $k$ 进行归纳。
当 $k=0$ 时,$S_k(n) = n$,结论成立。
当 $k=d$ 时:

通过二项式定理化简,提出一项相消,有:
$$\begin{aligned} &(i+1)^{d+1} - i^{d+1}\\ = &\sum_{j=0}^{d+1}\left(\begin{matrix}d+1\\j\end{matrix}\right)i^j - i^{d+1}\\ = &\sum_{j=0}^{d}\left(\begin{matrix}d+1\\j\end{matrix}\right)i^j \end{aligned}$$

对 $(i+1)^{d+1} - i^{d+1}$ 求和,有:

$$\begin{aligned}&\sum_{i=1}^{n}\left\{(i+1)^{d+1} - i^{d+1}\right\}\\=&\sum_{i=1}^{n}\sum_{j=0}^{d}\left(\begin{matrix}d+1\\j\end{matrix}\right)i^j\end{aligned}$$

发现 $\left(\begin{matrix}d+1\\j\end{matrix}\right)$ 只与 $j$ 有关,调换求和顺序,有:

$$\begin{aligned}&\sum_{i=1}^{n}\sum_{j=0}^{d}\left(\begin{matrix}d+1\\j\end{matrix}\right)i^j\\=&\sum_{j=0}^{d}\left(\begin{matrix}d+1\\j\end{matrix}\right)\sum_{i=1}^{n}i^j\\=&\sum_{j=0}^{d}\left(\begin{matrix}d+1\\j\end{matrix}\right)S_j(n)\end{aligned}$$

化出了有趣的玩意。
展开左侧 $i^{d+1}$ 的求和式相消,则有:

$$(n+1)^{d+1} - 1 = \sum_{j=0}^{d}\left(\begin{matrix}d+1\\j\end{matrix}\right)S_j(n)$$

提出右侧 $j=d$ 时的 $S_d(n)$:

$$\left(\begin{matrix}d+1\\d\end{matrix}\right)S_d(n) = (n+1)^{d+1} -\sum_{j=0}^{d-1}\left\{\left(\begin{matrix}d+1\\j\end{matrix}\right)S_j(n)\right\} - 1$$

二项式定理展开右侧,并略做处理:

$$S_d(n) = \dfrac{1}{d+1}\left\{\sum_{j=0}^{d+1}n^j -\sum_{j=0}^{d-1}\left\{\left(\begin{matrix}d+1\\j\end{matrix}\right)S_j(n)\right\} - 1\right\}$$

对于右侧,通过数学归纳得到 $S_j(n)$ 为关于 $n$ 的 $j$ 次多项式。
则整个式子最高次项出现在 $\sum\limits_{j=0}^{d+1}n^j$ 中,次数为 $d+1$。
得证。

具体实现

拉格朗日插值是啥?拉格朗日插值

由性质,$S_k(n)$ 为关于 $n$ 的 $k + 1$ 次多项式,需要 $k+2$ 个点值进行构造。
可以直接取 $k+1$ 个点,按照定义计算出 $S_k(n)$,构造多项式。
复杂度 $O(k^2)$?我觉得不行。

题目对选择的点并没有要求,考虑选取一段连续的点进行优化。
使 $x_i = i$,则选择的点集为 $\{(i, S_k(i))\, \mid \, i \in \N^+, i\le k+2\}$。
按照定义递推出来即可,复杂度 $O(k \log k)$。

考虑要求的点 $(n, S_k(n))$,将其代入插值公式,有:
$$S_k(n)= \sum_{i=1}^{k+2}S_k(i)\prod_{i\not ={j}}\dfrac{n-j}{i-j}$$

发现乘积项的分母与 $n$ 无关,提出来:

$$S_k(n)= \sum_{i=1}^{k+2}S_k(i)\dfrac{\prod\limits_{i\not ={j}}{(n-j)}}{\prod\limits_{i\not ={j}}(i-j)}$$

手玩一下乘积项的变化规律。

对于分母,$j\le k +2$,在已知 $i$ 时有:
$$\begin{aligned} &\dfrac{1}{\prod\limits_{i\not ={j}}(i-j)}\\ = &\dfrac{1}{i(i-1)(i-2) \dots 1 \times(-1) \dots (k+2-i-1)(k+2-i)}\\=&(-1)^{k+2-i}\dfrac{1}{i! (k+2-i)!} \end{aligned}$$

可先预处理阶乘再求逆元,快速得到分母的值。

对于分子,也暴力拆一波:

$$\begin{aligned} &\prod\limits_{i\not ={j}}{(n-j)}\\ =& n(n-1) \dots (n-(i-1))(n-(i+1))\dots (n-(k+2))\\ =&(\prod_{j=1}^{i-1}(n-j)) (\prod_{j=i+1}^{k+2}(n-j))& \end{aligned}$$

考虑维护 $(n-j)$ 的 前/后 缀积,可快速得到分子的值。

则有:

$$S_k(n)= \sum_{i=1}^{k+2}(-1)^{k+2-i}S_k(i)\dfrac{(\prod\limits_{j=1}^{i-1}(n-j)) (\prod\limits_{j=i+1}^{k+2}(n-j))}{i! (k+2-i)!}$$

复杂度

$O(k \log k)$ 处理 $k+2$ 个连续点值。$O(n)$ 预处理前/后 缀积,阶乘。
求逆元时可以 $O(n)$ 预处理,也可以单次 $O(\log k)$。

总复杂度 $O(k\log k)$。

优缺点

优点:简单好写,复杂度优秀,就感觉到快。

缺点:出现了除法,需要求逆元,需保证模数为质数。

若模数不为质数怎么办? 可利用 斯特林数/伯努利数 求解。
伯努利数求解方法 详见 皎月半洒花的题解

斯特林数求解方法 复杂度 $O(k^2)$,无法通过本题,详见 自然数幂之和 - Luckyblock


代码实现

//知识点:拉格朗日插值
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#define ll long long
const int MARX = 1e6 + 10;
const ll mod = 1e9 + 7;
//=============================================================
ll N, K, tmp, ans, pre[MARX], suf[MARX], fac[MARX];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
ll qpow(ll x, ll y, ll Mod) {
  ll ret = 1;
  for (; y; x = x * x % Mod, y >>= 1)
    if (y & 1) ret = ret * x % Mod;
  return ret;
}
//=============================================================
int main() {
  N = read(), K = read();
  pre[0] = suf[K + 3] = fac[0] = 1;
  for (ll i = 1; i <= K + 2; i++) pre[i] = pre[i - 1] * (N - i) % mod;
  for (ll i = K + 2; i >= 1; i--) suf[i] = suf[i + 1] * (N - i) % mod;
  for (ll i = 1; i <= K + 2; i++) fac[i] = fac[i - 1] * i % mod;

  for (int i = 1; i <= K + 2; i++) {
    tmp = (tmp + qpow(i, K, mod)) % mod;
    ll a = pre[i - 1] * suf[i + 1] % mod;
    ll b = fac[i - 1] * ((K - i) & 1 ? -1 : 1) * fac[K + 2 - i] % mod;
    ans = (ans + tmp * a % mod * qpow(b, mod - 2, mod) % mod) % mod;
  }
  printf("%lld\n", (ans + mod) % mod);
  return 0;
}

写在最后

参考资料:
拉格朗日插值 - OI Wiki
皎月半洒花的题解