codeforces-622F

题目链接

622f

思路

$$Ans=\sum_{i=1}^n i^k$$

直接求肯定会超时，然后自然数幂和可以表达为k+1项的多项式。

自然数幂和展开多项式

$$(n+1)^k-(n^k)=\sum_{i=0}^{k-1}C_k^in^i\\ n^k-(n-1)^k=\sum_{i=0}^{k-1}C_k^i(n-1)^i\\ \vdots\\ 累加得到\\ \sum_{i=1}^n((i+1)^k-i^k)=(n+1)^k-1\\ =\sum_{i=1}^n\sum_{j=1}^{k-1}C_k^ji^j\\ =\sum_{i=0}^{k-1}C_k^j\sum_{j=1}^nj^i\\ 设f(j)=\sum_{i=1}^ni^j\\ =\sum_{i=1}^{k-1}C_k^jf(j)\\ =\sum_{i=0}^{k-2}C_k^jf(j)+k*f(k-1)\\$$

取出方程

$$\begin{aligned} (n+1)^k-(n^k)&=\sum_{i=0}^{k-2}C_k^jf(j)+k*f(k-1)\\ 移项\\ f(k-1)&=\frac{(n+1)^k-n^k-\sum_{i=0}^{k-2}C_k^jf(j)}{k}\\ f(k)&=\frac{(n+1)^{k+1}-n^{k+1}-\sum_{i=0}^{k-1}C_(k+1)^jf(j)}{k+1}\\ \end{aligned}$$ $$最后得到$$ $$\sum_{i=1}^ni^k=\frac{(n+1)^{k+1}-n^{k+1}-\sum_{i=0}^{k-1}C_(k+1)^jf(k)}{k+1}$$

得到自然数幂和的形式肯定是一个k+1项的多项式，这样就能够使用拉格朗日插值了

拉格朗日插值

对应某个多项式函数，已知的有k+1个取值点，即在二维平面上存在k+1个点,$(x_0,y_0),\cdots,(x_k,y_k)$
假设任意两个$x_i!=x_j$，然后就可以应用拉格朗日插值多项式表达为$L(x)=\sum_{j=0}^ky_j\ell_j(x)$

此处$\ell_j(x)$就是拉格朗日基本多项式（插值基函数），表达式为

$\ell_j(x) = \prod_{i=0,i!=j}^k\frac{x-x_i}{x_j-x_i}$

$\ell_j(x)的特点就是仅仅在x_j上取值为1，其他店x_i,i!=j上取值为0$，这样如果我们能够求出来$y_j和\ell_j(x)$就可以求出整个多项式的值

思路

根据第一个差分表示法，我们直到自然数幂和$\sum_{i=1}^ni^k$可以表达成k+1次幂的和，然后我们就用拉格朗日插值法，插1,2,3,4…k+2即可,然后我们得到多项式的式子为

$$L(n)=\sum_{j=0}^ky_j\ell_j(x)\\ y_j=\sum_{i=1}^ji^k\\ \ell_j(n)=\prod_{i=1,i!=j}^k\frac{(n-1)*(n-2)\dotsb(n-k)/(n-i)}{(x_j-1)*(x_j-2)\dotsb(x_j-k)}\ y_j可以直接处理出来，然后\ell_j(n)的分资也可以预处理出来，现在考虑分母\\ 发现实际上它也是前缀和，分成两个部分，一个正的一个负的\\ 例如x_j=3时。得到1*2*(-1)*(-2)*(-3)\dotsb(-k+3)，显然这部分也能够预处理出来\\$$

然后这题就写完了

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define inv(x) quick_pow(x,mod-2)
const int N = 1e6+10;
ll g[N],f[N],x[N];
ll quick_pow(ll x,ll k){
	ll res=1;
	while(k){
		if(k&1)res=res*x%mod;
		x=x*x%mod;
		k>>=1;
	}
	return res;
}
ll a[N];
int main(){
	int n,k;
	scanf("%d %d",&n,&k);
	g[0]=x[0]=1;
	for(int i=1;i<=k+2&&i<=n;i++)f[i]=(f[i-1]+quick_pow(i,k))%mod;
	if(k+2>=n)
	return 0*printf("%lld\n",f[n]);
	ll now = 1; 
	for(int i=1;i<=k+2;i++){
		now=(now*(n-i))%mod;
		x[i]=x[i-1]*i%mod;
		g[i]=-g[i-1]*i%mod;
	}
	ll ans=0;
	for(int i=1;i<=k+2;i++){
		ans=(ans+f[i]*now%mod*inv(n-i)%mod*inv((x[i-1]*g[k+2-i])%mod)%mod)%mod;
	}
	printf("%lld\n",(ans+mod)%mod);
}