题目#

题解#

设 $F(n) = \sum _{i=1}^n{i^k}$ ，当k很小的时候，可以找到一些通项公式，比如：当 $k= 1$ 时， $F(n) = \frac{(n \cdot (n+1))}{2}$ ，当 $k=2$ 时， $F(n)= \frac{n \cdot \ (2 \cdot n + 1) \cdot (n+1)}{6}$ 。

可以发现， $F(n)$ 实际上是一个 $k+1$ 次多项式函数。

因此，我们就可以使用拉格朗日插值法来推导了。

确定一个k+1次多项式需要k+2个点，我们很容易通过打表得到 $F(1) \sim F(k+2)$ 的值。

然后代入插值公式：

$F(n) = \sum_{i=1}^{k+2}F(i) \times P(i)$

$P(i) = \prod_{j=1, j \neq i}^{k+2}\frac{n-j}{i-j}$

所以

$\begin{aligned}F(n) &= \sum_{i=1}^{k+2}F(i) \times \prod_{j=1, j \neq i}^{k+2}\frac{n-j}{i-j} \\ &= \sum_{i=1}^{k+2}F(i) \times \frac{\prod_{j=1, j \neq i}^{k+2}n-j}{\prod_{j=1, j \neq i}^{k+2}{i-j}}\end{aligned}$

但是这个公式的复杂度时 $O(k^2)$ 的，我们再优化一下。

设 $T = \prod_{j=1}^{k+2}{n-j}$ ，则

$\prod_{j=1, j \neq i}^{k+2}n-j = \frac{T}{n-i}$

对于 $\prod_{j=1, j \neq i}^{k+2}{i-j}$ ，我们将它分成 $i\lt j$ 和 $i\gt j$ 两部分来考虑，

$\prod_{j=1, j \neq i}^{k+2}{i-j} = (i-1)!\times(k+2-i)!\times (-1)^{k+2-i}$

带入原式，得：

$F(n) = \sum_{i=1}^{k+2}(F(i)\times\frac{T}{n-i}\times\frac{1}{(i-1)!\times(k+2-i)!\times (-1)^{k+2-i}})$

至此，我们可以通过打表的方式，在 $O(k)$ 时间内得到 $F(n)$ 了。

注意#

当 $n \leq k+2$ 时，该公式时不适用的，因为 $T$ 会为 $0$ 。

但是我们可以直接通过 $F(n) = \sum _{i=1}^n{i^k}$ 计算。

代码#

1
/*---------------------------------
2

3
 @Author:   Dicer
4
 @DateTime: 2019-06-18 10:16:23
5

6
---------------------------------*/
7

8
#include <bits/stdc++.h>
9
using namespace std;
10
typedef long long ll;
11
typedef pair<int, int> pii;
12
inline ll qpow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res = (res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
13
const double eps = 1e-8;
14
const int INF = 0x3f3f3f3f;
15
const int mod = 1e9+7;
16
const int MAXN = 1e6 + 7;
17

18
ll F[MAXN], fac[MAXN], T;
19
int n, k;
20

21
ll inv(ll x){
22
  return qpow(x, mod-2, mod);
23
}
24
void init(){
25
  F[1] = 1;
26
  for(int i = 2; i <= k+2; ++i){
27
    F[i] = F[i-1] + qpow(i, k, mod);
28
    F[i] %= mod;
29
  }
30
  fac[0] = 1;
31
  for(int i = 1; i <= k+2; ++i){
32
    fac[i] = fac[i-1] * i;
33
    fac[i] %= mod;
34
  }
35
  T = 1;
36
  for(int i = 1; i <= k+2; ++i){
37
    T *= n - i;
38
    T %= mod;
39
  }
40
}
41
void solve(){
42
  if(n <= k+2){
43
    ll res = 0;
44
    for(int i = 1; i <= n; ++i){
45
      res += qpow(i, k, mod);
46
      res %= mod;
47
    }
48
    cout << res << endl;
49
    return;
50
  }
51
  ll res = 0;
52
  for(int i = 1; i <= k+2; ++i){
53
    res += F[i] * T % mod * inv(n-i) % mod * inv(fac[i-1]) %mod * inv(fac[k+2-i]) %mod * ((k-i)%2 == 0?1:-1) %mod;
54
    res += mod;
55
    res %= mod;
56
  }
57
  cout << res << endl;
58
}
59
int main(int argc, char const *argv[])
60
{
61
  cin >> n >> k;
62
  init();
63
  solve();
64
  return 0;
65
}

Reference#

本文题图由User.ca - Self-made, based on Image.png，CC BY-SA 3.0，https://commons.wikimedia.org/w/index.php?curid=5538041
参考文章
LaTex