正題

題目鏈接:https://www.luogu.com.cn/problem/CF622F

---

題目大意

給出$n,k$，求
$$\sum _{i=1}^n{i}^k$$

---

解題思路

很經典的拉格朗日差值問題
這個東西顯然是可以化成一個$k+1$次的多項式的，所以我可以直接代$k+2$個點插出值來。看到順眼先把$n,k$互換一下。
先上一個要刻在$DNA$里的公式$$f(k)=\sum _{i=1}^n{y}_i\prod _{j=1,j=i}^n\frac{x_j?k}{x_i?x_j}$$
發現這個直接計算是$O(n^2)$的搞不定。
上面的$x_j?k$挺好優化的，分別做一個前后綴積就好了，但是麻煩的是$x_i?x_j$。我們可以利用$x_i$是連續的這個性質，我們只需要帶入$x_i\in [1,n+2]$的點即可。

此時$x_i?x_j$就變為了兩段階乘分別是${\prod }_{j=1}^{i?1}\frac{1}{i?j}$和${\prod }_{j=i+1}^j\frac{1}{i?j}$。預處理逆元前綴和就好了，需要注意的是因為后面那個式子$i?j$是負數所以我們需要判斷一下如果$n?i$是奇數就要取反。

線性篩$y_i$的話時間復雜度$O(n)$，懶得話直接快速冪$O(n\log k)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e6+10,P=1e9+7; ll n,k,ans,inv[N],suf[N],pre[N]; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } signed main() {scanf("%lld%lld",&k,&n);// if(k<=n+2){// for(ll i=1;i<=k;i++)// ans=(ans+power(i,n))%P;// printf("%d\n",ans);// return 0;// }inv[1]=1;n+=2;for(ll i=2;i<=n;i++)inv[i]=P-(P/i)*inv[P%i]%P;inv[0]=1;for(ll i=1;i<=n;i++)inv[i]=inv[i-1]*inv[i]%P;ll tmp=1;pre[0]=suf[n+1]=1;for(ll i=1;i<=n;i++)pre[i]=pre[i-1]*(k-i)%P;for(ll i=n;i>=1;i--)suf[i]=suf[i+1]*(k-i)%P;for(ll i=1,p=0;i<=n;i++){(p+=power(i,n-2))%=P;ans+=p*pre[i-1]%P*suf[i+1]%P*inv[i-1]%P*(((n-i)&1)?P-inv[n-i]:inv[n-i])%P;ans=ans%P;}printf("%lld\n",(ans+P)%P);return 0; }

總結

以上是生活随笔為你收集整理的CF622F-The Sum of the k-th Powers【拉格朗日插值】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。