题目链接
622f
思路
直接求肯定会超时,然后自然数幂和可以表达为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即可,然后我们得到多项式的式子为
然后这题就写完了
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| #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); }
|