题目链接

Solution CF622F The Sum of the k-th Powers

题目大意：给定\(i,k\),求\(\sum_{i=1}^ni^k\)

拉格朗日插值

---

分析：首先类似于积分，自然数\(k\)次幂的前缀和\(F(n)\)可以用一个\(k + 1\)次的多项式表达出来

那么我们就可以选取\(k + 2\)个点，用拉格朗日插值求出\(F(n)\)

注意，如果随便选择点的话时间复杂度是\(O(k^2)\)的，我们通过选取连续的点可以做到\(O(k)\)

\(F(n)=\sum_{i=1}^{k+2}(i^k \cdot \frac{\prod_{j \neq i}n-j}{\prod_{j \neq i}i-j})\)

首先观察分子，我们可以通过讨论\(n\)和\(k+2\)的大小关系，如果\(n \leq k + 2\)那么我们就暴力算，否则插值，这样可以避免分子的符号讨论

对于分子，我们只需要预处理出\(n-i \quad i \in [1,k+2]\)的前、后缀积就可以\(O(1)\)求得

对于分母，观察发现实质上是两个阶乘之积，只不过要根据\(k+2-i\)的奇偶性来讨论符号

\(i^k\)可以快速幂在\(O(logk)\)的时间内求得

总复杂度\(O(klogk)\)

#include <cstdio>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7,maxk = 1e6 + 100;
typedef long long ll;
ll ans,fac[maxk],suf[maxk],pre[maxk],sum;
int n,k;
ll add(ll a,ll b){return (a + b) % mod;}
ll mul(ll a,ll b){return (a * b) % mod;}
ll qpow(ll a,ll b){
	ll res = 1,base = a;
	while(b){
		if(b & 1)res = mul(res,base);
		base = mul(base,base);
		b >>= 1;
	}
	return res;
}
ll inv(ll x){return qpow(x,mod - 2);}
ll pro(ll a,ll b){
	return mul(fac[b],inv(fac[a - 1]));
}
inline void init(){
	fac[0] = pre[0] = suf[k + 3] = 1;
	for(int i = 1;i <= k + 2;i++)fac[i] = mul(fac[i - 1],i);
	for(int i = 1;i <= k + 2;i++)pre[i] = mul(pre[i - 1],n - i);
	for(int i = k + 2;i >= 1;i--)suf[i] = mul(suf[i + 1],n - i);
}
int main(){
	scanf("%d %d",&n,&k);
	if(n <= k + 2){
		for(int i = 1;i <= n;i++)ans = add(ans,qpow(i,k));
		printf("%lld\n",ans);
		return 0;
	}
	init();
	for(int i = 1;i <= k + 2;i++){
		ll s1 = 1,s2 = 1;
		if(i != 1)s1 = mul(s1,pre[i - 1]);
		if(i != k + 2)s1 = mul(s1,suf[i + 1]);

		if(i != 1)s2 = mul(s2,pro(1,i - 1));
		if(i != k + 2)s2 = mul(s2,((k + 2 - i) % 2) ? (mod - pro(1,k + 2 - i)) : pro(1,k + 2 - i));

		sum = add(sum,qpow(i,k));
		ans = add(ans,mul(sum,mul(s1,inv(s2))));
	}
	printf("%lld\n",ans);
	return 0;
}