「笔记」自然数幂之和 |
您所在的位置:网站首页 › 自然数规律公式 › 「笔记」自然数幂之和 |
目录定义性质暴力计算差分法复杂度优缺点:拉格朗日插值复杂度优缺点第一类斯特林数引理 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}\) 的求和式相消,则有: \[(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\)。 得证。 暴力计算看起来很快的 \(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}\]拆开求和符号。 对于第一项,转化为组合数。 使用组合数性质合并,再展开组合数,有: \[\begin{aligned} &\sum\limits_{i=1}^{n}i^{\underline{k}}\\ =&k!\sum_{i=1}^{n}\dfrac{i^{\underline{k}}}{k!}\\ =&k!\sum_{i=1}^{n}{\displaystyle\left(\begin{matrix}i\\k\end{matrix}\right)}\\ =&k!{\displaystyle\left(\begin{matrix}n+1\\k+1\end{matrix}\right)}\\ =&\dfrac{(n+1)^{\underline{k+1}}}{k+1} \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 级学弟学妹来啦! |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |