「Codeforces 622F」The Sum of the k-th Powers（多项式）

题目大意

「Codeforces 622F」The Sum of the k-th Powers

求 $\sum_{i = 1}^{n} i^k \bmod 10^9 + 7$。

数据范围：$n \le 10^9, k \le 10^6$。

思路分析

直接做显然是不行的，我们猜想 $\sum_{i = 1}^{n} i^k$ 是一个 $k + 2$ 次多项式。我们先对于 $1 \le i \le k + 2$ 计算出 $a_i = \sum_{j = 1}^{i} j^k$ 的值，然后使用拉格朗日插值来求出该多项式在 $n$ 处的值即可。然而拉格朗日插值的复杂度是 $O(k^2)$ 的，不能通过此题。

考虑拉格朗日插值的过程。根据拉格朗日插值公式，答案为：

$$\begin {align} f(n) &= \sum_{i} a_i \prod_{i \neq j} \frac{n - j}{i - j} \\ &= \left( \prod_{i} (n - i) \right) \times \sum_i \frac{a_i}{n - i} \prod_{i \neq j} \frac{1}{i - j} \\ &= \left( \prod_{i} (n - i) \right) \times \sum_i \frac{a_i}{n - i} \left( \prod_{i > j} \frac{1}{i - j} \times \prod_{i < j} \frac{1}{i - j} \right) \end {align}$$

而我们有：

$$\prod_{i > j} \frac{1}{i - j} \times \prod_{i < j} \frac{1}{i - j} = (i - 1)! \times (-1)^{k + 2 - i} (k + 2 - i)!$$

所以我们只需要预处理阶乘即可计算答案了。由于一开始的 $k$ 次方和计算和计算答案时需要求逆元，时间复杂度为 $O(k \log k)$。

能不能线性呢？答案是肯定的。注意到 $\text{ID}_k(x)$ 是完全积性函数，我们可以使用线性筛在 $O(k + \frac{k \log k}{\ln k}) = O(k)$ 的时间内算出它的前缀和。对于逆元，我们只需要使用线性求逆元的科技即可。这样，时间复杂度就优化成了 $O(k)$。

代码实现

#include <cstdio>