Skip to main content

__debug's Home Keep it simple, stupid

计算自然数幂和

相关文章: 计算自然数幂和 II.

问题

给定 \(n\), \(k\), 求 \(\sum_{i = 0}^{n}i^k\). 其中 \(n\) 非常大.

做法

做法一:递推

首先递推式不能跟 \(n\) 有关,否则…… 所以一定要出现 \(\sum_{i = 0}^{n}i^k\) 此类. 不妨利用差分的思想.

首先作差

$$(i + 1)^{k + 1} - i^{k + 1} = \binom{k + 1}{1}i^k + \binom{k + 1}{2} i^{k - 1} + ... + \binom{k + 1}{k}i + 1$$

然后搞一搞前缀和

$$(n + 1)^{k + 1} - 1 = \binom{k + 1}{1}\sum\limits_{i = 0}^{n}i^k + \binom{k + 1}{2}\sum\limits_{i = 0}^{n}i^{k-1} + ... + \binom{k + 1}{k}\sum\limits_{i = 0}^{n}i + n$$

整理一下 $$\sum\limits_{i = 0}^{n}i^k = \frac{1}{k + 1} \left[(n + 1)^{k + 1} - \left(\binom{k + 1}{2}\sum\limits_{i = 0}^{n}i^{k-1} + ... + \binom{k + 1}{k}\sum\limits_{i = 0}^{n}i + n + 1\right)\right]$$

大功告成! 时间复杂度 \(O(k^2)\).

做法二: Stirling 数

UPD 2017.07.12: 发现原来傻逼了… 直接用下降幂和离散微积分直接得多.

我来填坑了… 最近遇到了一些恶心题, 不得不用这种方法.

思考当题目要求模 \(p\) 意义下的答案, 而 \(p\) 不为质数时怎么办呢?

必备技能(参考"具体数学"):

  • 下降幂: \(x^{\underline{n}} = \frac{x!}{(x-n)!}\)
  • 第一类斯特林数: \(\left[\begin{matrix} n \\ k \end{matrix}\right] = (n - 1)\left[\begin{matrix} n - 1 \\ k \end{matrix}\right] + \left[\begin{matrix} n - 1 \\ k - 1 \end{matrix}\right]\)

然后我先放几个要用到的恒等式(同样参考"具体数学"): $$\begin{aligned} x^{\underline{n}} = \sum_{k = 0}^{n} \left[\begin{matrix} n \\ k \end{matrix}\right] (-1)^{n - k} x^k \\ \\ \sum_{k = 0}^{n} \binom{k}{m} = \binom{n + 1}{m + 1} \end{aligned}$$

好了, 现在进入正题. 下面的做法主要参考了 GEOTCBRL 某题的题解.

容易发现 $$\begin{aligned} \binom{n}{k} = \frac{n^{\underline{k}}}{k!} = \frac{\sum\limits_{i = 0}^{k} \left[\begin{matrix} k \\ i \end{matrix}\right] (-1)^{k - i} n^i}{k!} \\ k! \binom{n}{k} = \sum_{i = 0}^{k} \left[\begin{matrix} k \\ i \end{matrix}\right] (-1)^{k - i} n^i \\ \\ n^k = k! \binom{n}{k} - \sum_{i = 0}^{\color{red}{k - 1}} \left[\begin{matrix} k \\ i \end{matrix}\right] (-1)^{k - i} n^i \end{aligned}$$

那么我们有 $$\begin{aligned} \sum_{i = 0}^{n} i^k &= \sum_{i = 0}^{n} \left( k! \binom{i}{k} - \sum_{j = 0}^{k - 1} \left[\begin{matrix} k \\ j \end{matrix}\right] (-1)^{k - j} i^j \right) \\ &= k! \sum_{i = 0}^{n} \binom{i}{k} - \sum_{i = 0}^{n} \sum_{j = 0}^{k - 1} \left[\begin{matrix} k \\ j \end{matrix}\right] (-1)^{k - j} i^j \\ &= k! \binom{n + 1}{k + 1} - \sum_{j = 0}^{k - 1} \left[\begin{matrix} k \\ j \end{matrix}\right] (-1)^{k - j} \color{red}{\sum_{i = 0}^{n} i^j} \\ &= \frac{(n + 1)^{\underline{k + 1}}}{k + 1} - \sum_{j = 0}^{k - 1} \left[\begin{matrix} k \\ j \end{matrix}\right] (-1)^{k - j} \color{red}{\sum_{i = 0}^{n} i^j} \end{aligned}$$

注意红色的项是之前已经求出的, 所以我们只需 \(O(k^2)\) 预处理出第一类斯特林数即可 \(O(k^2)\) 递推计算.

等等… 不是还有一个 \(k + 1\) 的分母吗?

不用担心, 看看分子, 发现是连续 \(k + 1\) 个自然数的乘积, 所以一定存在 \(k + 1\) 的一个因子! 问题至此迎刃而解.

Comments

Comments powered by Disqus