拉格朗日插值

公式

$f(x)=\sum_{i=0}^ny_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}\\$
$f(x)$ 是 $n$ 次多项式
复杂度为 $O(n^2)$
一些特殊条件下可以优化

一道裸题

题目传送门：622F-The Sum of the k-th Powers

题目大意

求 $\sum_{i=1}^{n}i^m(\mod 10^9+7)$
因为模数的关系，显然不可以 $NTT$
这题其实是拉格朗日插值的裸题

解题思路

令 $f(n)=\sum_{i=1}^ni^m$
通过低次的规律可以发现， $f(n)$ 应该是一个 $m+1$ 次的多项式，我们可以通过拉格朗日插值求出 $f(0)$ 到 $f(m+1)$ 然后就可以求出其他的每个值了
则原式变为 $\sum_{i=0}^{m+1}f(i)\prod_{j\ne i}\frac{n-j}{i-j}\\$
观察后半部分可以发现，分母其实是两个阶乘相乘再乘上一个 $(-1)^k$ 形式的系数
而分子同样可以看作是两个以 $i$ 为分界的两段连乘
则原式变为 $\sum_{i=0}^{m+1}f(i)(-1)^{m+1-i}\frac{\prod_{j=n-i+1}^{n}\prod_{j=n-m-1}^{n-i-1}}{i!(m+1-i)!}$
分母的阶乘范围在 $\left[0!,(m+1)!\right]$ ,而分子的连乘也就只有 $m+1$ 个值，可以预处理
记 $pre_i=\prod_{j=n-i+1}^{n}j\\$
$suf_i=\prod_{n-m-1}^{n-i-1}\\$
$fac_i=i!\\$
则原式变为 $\sum_{i=0}^{m+1}f(i)(-1)^{m+1-i}\frac{pre_i*suf_i}{fac_i*fac_{m+1-i}}$
其中 $fac_i^{-1}\equiv fac_{i+1}^{-1}*(i+1)(\mod P)\\$
只需要求 $fac_{m+1}$ 的逆元，然后 $O(m)$ 预处理其他逆元即可

$g(i)=i^m$ 显然是一个积性函数，可以欧拉筛，但是每个求一遍逆元也可以接受
最后枚举 $i$ 求和即可

本题模板

//#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
// #define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<ll, ll> pii;
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
const int maxn = 1e6 + 10;
ll fac[maxn], pre[maxn], suf[maxn], infac[maxn];
ll f[maxn];
ll qmod(ll a,ll n)
{
    ll ans = 1;
    while(n)
    {
        if (n & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

int main()
{
    ll n, m;
    ll d;
    read(n), read(m);
    d = m + 1;
    f[0] == 0;
    fac[0] = 1;
    for (int i = 1; i <= d; ++i)
    {
        fac[i] = fac[i - 1] * i % mod;
        f[i] = (f[i - 1] + qmod(i, m)) % mod % mod;
    }
    infac[d] = qmod(fac[d], mod - 2);
    for (int i = d - 1; i >= 0; --i)
    {
        infac[i] = infac[i + 1] * (i + 1) % mod;
    }
    if (n <= d)
    {
        printf("%lld\n", f[n]);
        return 0;
    }
    pre[0] = 1;
    suf[d] = 1;
    for (int i = 1; i <= d; ++i)
    {
        pre[i] = pre[i - 1] * (n - i + 1) % mod;
    }
    for (int i = d; i >= 1; --i)
    {
        suf[i - 1] = suf[i] * (n - i) % mod;
    }
        ll res = 0;
    for (int i = 0; i <= d; ++i)
    {
        ll ret = f[i] * pre[i] % mod * suf[i] % mod * infac[d - i] % mod * infac[i] % mod;
        if ((d - i) & 1)
            res = (res - ret + mod) % mod;
        else
            res = (res + ret) % mod;
    }
    printf("%lld\n", res);
}