「笔记」自然数幂之和
- 定义
- 性质
- 暴力计算
- 差分法
- 复杂度
- 优缺点:
- 拉格朗日插值
- 复杂度
- 优缺点
- 第一类斯特林数
- 引理 1
- 引理 2
- 证明
- 复杂度
- 优缺点
- 伯努利数
- 题目
- 写在最后
学到许多。
定义
定义前 \(n\) 个自然数 \(k\) 次幂的和为:
\[S_k(n) = \sum_{i=1}^{n}i^k \]性质
\(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}\) 的求和式相消,则有:
提出右侧 \(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\)。
得证。
暴力计算
看起来很快的 \(O(n\log k)\)?
唯一一个复杂度依赖 \(n\) 的算法,会被卡爆。
差分法
在性质证明过程的最后,得到了一个优美的式子:
\[S_k(n) = \dfrac{1}{k+1}\left\{\sum_{j=0}^{k+1}n^j -\sum_{j=0}^{k-1}\left\{\left(\begin{matrix}k+1\\j\end{matrix}\right)S_j(n)\right\} - 1\right\} \]已知 \(S_0(n) = n\),显然可以进行递推。
复杂度
显然的 \(O(k^2)\)。
优缺点:
优点:无。
缺点:需要求解 \(k+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)\)。
优缺点
优点:简单好写,复杂度优秀,就感觉到快。
缺点:出现了除法,需要求逆元,需保证模数为质数。
第一类斯特林数
斯特林数是啥? 。
\[S_k(n) = \dfrac{(n+1)^{\underline{k+1}}}{k+1} -\sum_{i=0}^{k-1} \cdot {\displaystyle \left[{\begin{matrix}k\\i\end{matrix}}\right]\,} \cdot S_i(n) \]引理 1
\[x^{\underline{n}} = (-1)^{n}(-x)^{\overline{n}} \]\[x^{\overline{n}} = (-1)^{n}(-x)^{\underline{n}} \]以式 1 为例:
暴力展开即可,有:
\[\begin{aligned} x^{\underline{n}} =& \prod_{i=0}^{n-1}(x-i)\\ =& (-1)^n \prod_{i=0}^{n-1}-(x-i)\\ =& (-1)^n \prod_{i=0}^{n-1}(-x + i)\\ =& (-1)^n (-x)^{\overline{n}} \end{aligned}\]式 2 同理可证。
引理 2
一个组合恒等式:
\[n^{\underline{k}} = \sum_{i=0}^{k}(-1)^{k-i}{\displaystyle \left[{\begin{matrix}k\\i\end{matrix}}\right]}n^{i} \]考虑 上升幂的性质
\[n^{\overline{k}} = \sum_{i=0}^{k}{\begin{bmatrix}k\\i\end{bmatrix}}n^{i} \]通过 引理 1 进行处理:
\[\begin{aligned} n^{\overline{k}} =& \sum_{i=0}^{k}{\begin{bmatrix}k\\i\end{bmatrix}}n^{i}\\ (-1)^k (-n)^{\underline{k}}=& \sum_{i=0}^{k}{\begin{bmatrix}k\\i\end{bmatrix}}n^{i} \end{aligned}\]等式两侧同乘 \((-1)^k\),有:
\[\begin{aligned} (-1)^k (-n)^{\underline{k}}=& \sum_{i=0}^{k}{\begin{bmatrix}k\\i\end{bmatrix}}n^{i}\\ (-n)^{\underline{k}}=& \sum_{i=0}^{k}{\begin{bmatrix}k\\i\end{bmatrix}}(-1)^k n^{i} \end{aligned}\]又有 \(i\le k\),提出 \((-1)^i\) 与 \(n^i\) 相乘,有:
\[\begin{aligned} (-n)^{\underline{k}}=& \sum_{i=0}^{k}{\begin{bmatrix}k\\i\end{bmatrix}}(-1)^k n^{i}\\ (-n)^{\underline{k}}=& \sum_{i=0}^{k}(-1)^{k-i}{\begin{bmatrix}k\\i\end{bmatrix}} (-n)^{i}\\ n^{\underline{k}}=& \sum_{i=0}^{k}(-1)^{k-i}{\begin{bmatrix}k\\i\end{bmatrix}} n^{i} \end{aligned}\]得证。
证明
观察引理,对于右侧的求和式,\(i=k\) 时,显然 \((-1)^{k-i}{\displaystyle \left[{\begin{matrix}k\\i\end{matrix}}\right]}n^{i}=n^k\),则
\[n^k = n^{\underline{k}} - \sum\limits_{i=0}^{k-1}(-1)^{k-i}{\displaystyle \left[{\begin{matrix}k\\i\end{matrix}}\right]}n^{i} \]对其求和,有:
\[\begin{aligned} S_k(n) &= \sum_{i=1}^{n}i^k \\ &= \sum_{i=1}^{n}\left\{{i^{\underline{k}}-\sum_{j=0}^{k-1}(-1)^{k-j}{\displaystyle \left[\begin{matrix}k\\j\end{matrix}\right]}i^j}\right\} \end{aligned}\]拆开求和符号。
对于第一项,转化为组合数。
使用组合数性质合并,再展开组合数,有:
对于第二项,只有 \(i^j\) 与 \(i\) 有关,交换求和符号,有:
\[\begin{aligned} &\sum_{j=0}^{k-1}(-1)^{k-j}{\displaystyle \left[\begin{matrix}k\\j\end{matrix}\right]}\sum_{1}^{n}i^j \\= &\sum_{i=0}^{k-1} \cdot {\displaystyle \left[{\begin{matrix}k\\i\end{matrix}}\right]\,} \cdot S_i(n) \end{aligned}\]得证。
复杂度
复杂度 \(O(k^2)\)。
需要预处理 \(k^2\) 个第一类斯特林数。
再递推求得 \(S_0(n), S_1(n)\dots S_k(n)\),单次复杂度为 \(O(k)\)。
优缺点
优点:模数可以为任意值,摆脱了质数的限制。
第一项 \(\dfrac{(n+1)^{\underline{k+1}}}{k+1}\) 看起来要求逆元,但 \((n+1)^{\underline{k+1}}\) 展开后至少有一项为 \(k+1\) 的倍数。
枚举 \(n+1-?\) 到 \(k+1\) 的倍数时直接除去 \(k+1\)即可。
缺点:TLE 警告。
伯努利数
?\(e\) 和 \(\infin\) 是个什么玩意
?多项式求逆
爬了。
会了 NTT 再回来
题目
CF622F The Sum of the k-th Powers
\(n\le 10^9, k\le 10^6\)。
只能用复杂度与 \(n\) 无关的算法过去(
写在最后
?我也不知道为什么叫差分法
可能是因为证明的时候用了 \(\sum\limits_{i=1}^{n}\left\{(i+1)^{d+1} - i^{d+1}\right\}\)。
63 级学弟学妹来啦!