題意

求\(\sum_{i=1}^n i^k\)，\(n \leq 10^9,k \leq 10^6\)

題解

觀察可得答案是一個\(k+1\)次多項式，我們找\(k+2\)個值帶進去然后拉格朗日插值

\(n+1\)組點值\((x_i,y_i)\)，得到\(n\)次多項式\(f\)的拉格朗日插值方法：

\[f(x) = \sum_{i = 0}^n y_i\prod_{j\not =i} \frac{x-x_j}{x_i-x_j}\]

時間復雜度為\(O(n^2)\).

現在考慮這題，我們把\(1\)到\(k+2\)帶入，有很好的性質：對于每個\(i\)，分母是\(1\)乘到\(i-1\)再乘上\(-1\)乘到\(i-k-2\)，這可以預處理階乘\(O(1)\)處理。分子可以預處理前后綴積來\(O(1)\)得到

于是時間復雜度為\(O(n)\)，可以通過

#include <algorithm> #include <cstdio> using namespace std;const int mo = 1e9 + 7; const int N = 1e6 + 10;int pl[N], pr[N], fac[N];int qpow(int a, int b) {int ans = 1;for(; b >= 1; b >>= 1, a = 1ll * a * a % mo)if(b & 1) ans = 1ll * ans * a % mo;return ans; }int main() {int n, k, y = 0, ans = 0;scanf("%d%d", &n, &k);pl[0] = pr[k + 3] = fac[0] = 1;for(int i = 1; i <= k + 2; i ++)pl[i] = 1ll * pl[i - 1] * (n - i) % mo;for(int i = k + 2; i >= 1; i --)pr[i] = 1ll * pr[i + 1] * (n - i) % mo;for(int i = 1; i <= k + 2; i ++)fac[i] = 1ll * fac[i - 1] * i % mo;for(int i = 1; i <= k + 2; i ++) {y = (y + qpow(i, k)) % mo;int a = pl[i - 1] * 1ll * pr[i + 1] % mo;int b = fac[i - 1] * ((k - i) & 1 ? -1ll : 1ll) * fac[k + 2 - i] % mo;ans = (ans + 1ll * y * a % mo * qpow(b, mo - 2) % mo) % mo;}printf("%d\n", (ans + mo) % mo);return 0; }

轉載于:https://www.cnblogs.com/hongzy/p/10371638.html

總結

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

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