「CF622F」The Sum of the k-th Powers「拉格朗日插值」
hongzy
·
·
题解
题意
求\sum_{i=1}^n i^k，n \leq 10^9,k \leq 10^6
题解
观察可得答案是一个k+1次多项式，我们找k+2个值带进去然后拉格朗日插值
$$f(x) = \sum_{i = 0}^n y_i\prod_{j\not =i} \frac{x-x_j}{x_i-x_j}$$
时间复杂度为$O(n^2)$.
现在考虑这题，我们把$1$到$k+2$带入，有很好的性质：对于每个$i$，分母是$1$乘到$i-1$再乘上$-1$乘到$i-k-2$，这可以预处理阶乘$O(1)$处理。分子可以预处理前后缀积来$O(1)$得到
于是时间复杂度为$O(n)$，可以通过
```cpp
#include <algorithm>
#include <cstdio>
using namespace std;
const int mo = 1e9 + 7;
const int N = 1e6 + 10;
int pl[N], pr[N], fac[N];
int qpow(int a, int b) {
int ans = 1;
for(; b >= 1; b >>= 1, a = 1ll * a * a % mo)
if(b & 1) ans = 1ll * ans * a % mo;
return ans;
}
int main() {
int n, k, y = 0, ans = 0;
scanf("%d%d", &n, &k);
pl[0] = pr[k + 3] = fac[0] = 1;
for(int i = 1; i <= k + 2; i ++)
pl[i] = 1ll * pl[i - 1] * (n - i) % mo;
for(int i = k + 2; i >= 1; i --)
pr[i] = 1ll * pr[i + 1] * (n - i) % mo;
for(int i = 1; i <= k + 2; i ++)
fac[i] = 1ll * fac[i - 1] * i % mo;
for(int i = 1; i <= k + 2; i ++) {
y = (y + qpow(i, k)) % mo;
int a = pl[i - 1] * 1ll * pr[i + 1] % mo;
int b = fac[i - 1] * ((k - i) & 1 ? -1ll : 1ll) * fac[k + 2 - i] % mo;
ans = (ans + 1ll * y * a % mo * qpow(b, mo - 2) % mo) % mo;
}
printf("%d\n", (ans + mo) % mo);
return 0;
}
```