2022.5.2$\rm lglrcz$
拉格朗日插值
\(\text{lglrcz}:f(x)=\sum\limits_{i=1}^n(y_i\cdot\prod\limits_{j\not=i}\dfrac{x-x_j}{x_i-x_j})\)
拉格朗日插值的用处在于在平方的时间内带入求解高次函数的特定值，其重点在于抽象化问题的函数模型及函数的次数和已知点。但是平方的时间复杂度并不是很优秀，所以一定要注意题目中具体式子的特点进行优化。
——沃茨?基硕徳
那么，借助\(\text{lglrcz}\)
已知 \(f(x)\) 的 \(n+1\) 个点，即可确定唯一的一个 \(n\) 次多项式。
由此不难延伸出 \(F(n,k)=\sum_{i=1}^n{i^k}\) 的求法。
首先，暴力计算所有的 \(F(i,k)\qquad i\in\Z,i\in[1,k+2]\) 。（因为 \(F(n,k)\) 是 \(k+1\) 次的）
相当于知道了 \((1,F(1,k)),(2,F(2,k)),...,(k+2,F(k+2,k))\) 这 \(k+2\) 个点。
于是，将这些点带入，有
\(F(n,k)=\sum\limits_{i=1}^n{i^k}=\sum\limits_{i=1}^{k+2}{[F(i,k)\cdot\prod_{j\not=i}{\dfrac{n-j}{i-j}}]}\)
还有一些 \(\text{lglrcz}\) 优化 \(dp\) 的技巧，以后再看。
点击查看代码
#include
#define int long long
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
inline void File() {
freopen("in.txt", "r", stdin);
freopen("Ans.txt", "w", stdout);
}
int n, k;
int pl[N], pr[N], fac[N];
int power(int x, int idx) {
if(!idx) return 1;
int t = power(x, idx >> 1) % mod;
return idx & 1 ? t * t % mod * x % mod : t * t % mod;
}
inline int inv(int x) {
return power(x, mod - 2) % mod;
}
inline int brute_force(int x, int y) {
int res = 0;
for(int i = 1; i <= x; i++) {
res = (res + power(i, y)) % mod;
}
return res;
}
struct A {
int x, y;
}a[N];
inline int lglrcz() {
int ans = 0ll, y = 0ll;
for(int i = 1; i <= k + 2; i++) {
/*int p1 = a[i].y % mod, p2 = 1ll;
for(int j = 1; j <= k + 2; j++) {
if(i == j) continue;
p1 = p1 * (n - a[j].x) % mod;
p2 = p2 * ((a[i].x - a[j].x) + mod) % mod;
}*/
y = (y + power(i, k)) % mod;
int p1 = pl[i - 1] * 1ll * pr[i + 1] % mod;
int p2 = fac[i - 1] * ((k - i) & 1 ? -1ll : 1ll) * fac[k + 2 - i] % mod;
ans = (ans + 1ll * y * p1 % mod * inv(p2) % mod) % mod;
}
return (ans + mod) % mod;
}
signed main() {
File();
cin >> n >> k;
pl[0] = pr[k + 3] = fac[0] = 1;
for(int i = 1; i <= k + 2; i++) {
a[i].x = i;
a[i].y = (a[i - 1].y + power(i, k)) % mod;
//printf("(%lld, %lld)\n", a[i].x, a[i].y);
}
for(int i = 1; i <= k + 2; i++)
pl[i] = 1ll * pl[i - 1] * (n - i) % mod;
for(int i = k + 2; i >= 1; i--)
pr[i] = 1ll * pr[i + 1] * (n - i) % mod;
for(int i = 1; i <= k + 2; i++)
fac[i] = 1ll * fac[i - 1] * i % mod;
#if false
if(n <= k + 2) {
cout << brute_force(n, k);
goto Z;
}
#endif
#if false
if(n <= k + 2) {
cout << a[n].y;
goto Z;
}
#endif
cout << lglrcz();
//Z:
return 0;
}