k次幂前缀和的线性做法

$\sum_{i=1}^{x} i^k \bmod p$

线性预处理逆元

$i^{-1} = -\left\lfloor \frac{p}{i} \right\rfloor \cdot (p \bmod i)^{-1} \bmod p$

$-\frac{\left\lfloor \frac{p}{i} \right\rfloor}{p-\left\lfloor \frac{p}{i} \right\rfloor i} = \frac{1}{i}$

拉格朗日插值法

$f(x) = \sum_{i=0}^{k+1} y_i l_i(x)$

$l_i(x) = \prod_{0 \leq m \leq k+1, m \neq i} \frac{x – x_m}{x_j – x_m}$

$f(n) = \sum_{i = 0}^{k+1} (-1)^{k+i+1} f(i) \frac{n(n-1) \cdots (n-i+1)(n-i-1) \cdots (n-d)}{(d-i)!i!}$

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ULL;

#define pow owahgrauhgso

ULL n, k, m;

ULL powmod(ULL b, ULL e) {
ULL r = 1;
while (e) {
if (e & 1) r = r * b % m;
b = b * b % m;
e >>= 1;
}
return r;
}

const int MAXN = 1000006;
ULL inv[MAXN];

void init_inv() {
inv[1] = 1;
for (int i = 2; i <= k+1; i++) {
inv[i] = (m - m / i) * inv[m % i] % m;
assert(inv[i] * i % m == 1);
}
}

ULL pow[MAXN];
ULL prime[MAXN], cnt;

void sieve() {
pow[1] = 1;
for (int i = 2; i <= k+1; i++) {
if (!pow[i]) {
pow[i] = powmod(i, k);
prime[cnt++] = i;
for (int j = 0; j < cnt && i*prime[j] <= k+1; j++) {
pow[i * prime[j]] = pow[i] * pow[prime[j]] % m;
if (i % prime[j] == 0) break;
}
}
}
}

ULL sum[MAXN];
ULL ans[MAXN];

auto addmod = [](ULL a, ULL b) -> ULL {return (a+b)%m;};

ULL lagrange() {
ULL p;
p = 1;
for (int i=0; i<=k+1; i++) {
if (i) p = p * inv[i] % m;
ans[i] = (k+1-i)&1 ? m-sum[i] : sum[i];
ans[i] = ans[i] * p % m;
p = p * (m + n - i) % m;
}
p = 1;
for (int i=k+1; i>=0; i--) {
if (k+1-i) p = p * inv[k+1-i] % m;
ans[i] = ans[i] * p % m;
p = p * (m + n - i) % m;
}
}