2023.5.21 闲话

第一次推出式子！

题意：

$\sum\limits_{i=m}^n i^k$

$n,m\leq 10^{12}$，$k\leq2000$。

题解：

众所周知 $k=1$ 时的情况

$\sum\limits_{i=1}^n i=\dfrac{n(n+1)}{2}$

先从证明 $k=2$ 的情况下手。熟知公式

$\sum\limits_{i=1}^n i^2=\dfrac{n(n+1)(2n+1)}{6}$

怎么来的呢？由二项式定理

$(n+1)^3=n^3+3n^2+3n+1$

即有

$(n+1)^3-n^3=3n^2+3n+1$

同理有

$\begin{aligned} (n+1)^3-n^3&=3n^2+3n+1 \\ n^3-(n-1)^3&=3(n-1)^2+3(n-1)+1 \\ &\cdots \\ 2^3-1^3&=3\cdot 1^2+3\cdot 1+1 \end{aligned}$

相加有

$(n+1)^3-1^3=3\sum\limits_{i=1}^n i^2+3\sum\limits_{i=1}^n i+1$

展开即证。

不妨将这个过程推广到一般情况上。考虑一般二项式定理

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

拿出左式的 $k+1$ 次项，重复上面的裂项过程

$\begin{aligned} (n+1)^{k+1}-n^{k+1}&=\sum\limits_{i=1}^{k+1}\binom{k+1}{i}n^{k+1-i} \\ n^{k+1}-(n-1)^{k+1}&=\sum\limits_{i=1}^{k+1}\binom{k+1}{i}(n-1)^{k+1-i} \\ &\cdots \\ 2^{k+1}-1^{k+1}&=\sum\limits_{i=1}^{k+1}\binom{k+1}{i}1^{k+1-i} \end{aligned}$

相加有

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

把右式 $k$ 次项拿出来，即得

$\sum\limits_{i=1}^n i^k=\dfrac{1}{k+1}\left((n+1)^{k+1}-1^{k+1}-\sum\limits_{i=2}^{k+1}\binom{k+1}{i}\sum\limits_{j=1}^n j^{k+1-i}\right)$

不妨令

$f(n,k)=\sum\limits_{i=1}^n i^k$

代入上式

$f(n,k)=\dfrac{1}{k+1}\left((n+1)^{k+1}-1^{k+1}-\sum\limits_{i=2}^{k+1}\binom{k+1}{i}f(n,k+1-i)\right)$

即得递推式。答案为

$f(n,k)-f(m-1,k)$

预处理组合数，时间复杂度 $O(k^2)$。

代码：

for (int i = 0; i <= 2001; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i && j <= 2001; j++)
        c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % p;
}
f[0] = n;
f[1] = mul(mul(n, n + 1), Pow(2, p - 2)) % p;
g[0] = m - 1;
g[1] = mul(mul(m - 1, m), Pow(2, p - 2)) % p;
for (int i = 2; i <= k; i++) {
    f[i] = (Pow(n + 1, i + 1) - 1) % p;
    g[i] = (Pow(m, i + 1) - 1) % p; 
    for (int j = 2; j <= i + 1; j++) {
        f[i] = ((f[i] - c[i + 1][j] * f[i + 1 - j] % p) % p + p) % p;
        g[i] = ((g[i] - c[i + 1][j] * g[i + 1 - j] % p) % p + p) % p;
    }
    f[i] = mul(f[i], Pow(i + 1, p - 2));
    g[i] = mul(g[i], Pow(i + 1, p - 2));
}