CONTENT: 拉格朗日插值法 I
DETAIL: 拉格朗日插值法、i^k的前缀和



Introduction


Note



【模板】拉格朗日插值 - luogu P4781

Description
由小学知识可知，n个点(xi,yi)可以唯一地确定一个多项式
现在，给定n个点，请你确定这个多项式，并将k代入求值
求出的值对998244353取模
Sample Input

3 100
1 4
2 9
3 16
3 100
1 1
2 2
3 3

Sample Output

10201
100

Solution

// luogu-judger-enable-o2
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MOD = 998244353;
const int N = 2000 + 15;

int x[N], y[N];

int quickPow(int a, int b, int MOD) {
    int ans = 1, base = a;
    while(b) {
        if(b & 1) {
            ans = (ll)ans * base % MOD;
        }
        base = (ll)base * base % MOD;
        b >>= 1;
    }
    return ans;
}

inline int calc(int k, int n) {
    int sum = 0;
    for(int i = 1; i <= n; i++) {
        int cur = y[i];
        for(int j = 1; j <= n; j++) {
            if(i == j) {
                continue;
            }
            cur = (ll)cur * (k - x[j] + MOD) % MOD * quickPow((x[i] - x[j] + MOD) % MOD, MOD - 2, MOD) % MOD;
        }
        sum = (sum + cur) % MOD;
    }
    return sum;
}

int main() {
    int n, k;
    while(~scanf("%d%d", &n, &k)) {
        for(int i = 1; i <= n; i++) {
            scanf("%d%d", &x[i], &y[i]);
        }
        printf("%d\n", calc(k, n));
    }
}


序列求和 V4 - 51NOD 1258

Description
T(n) = n^k，S(n) = T(1) + T(2) + …… T(n)。给出n和k，求S(n)。
例如k = 2，n = 5，S(n) = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 55。
由于结果很大，输出S(n) Mod 1000000007的结果即可。
Sample Input

3
5 3
4 2
4 1

Sample Output

225
30
10

Solution

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int N = 50000 + 15;

int inv[N];
int prime[N], tot;
int fi[N];
int ans[N];

inline int quickPow(int a, int b) {
    int ans = 1, base = a;
    while(b) {
        if(b & 1) {
            ans = (ll)ans * base % MOD;
        }
        base = (ll)base * base % MOD;
        b >>= 1;
    }
    return ans;
}

inline void initInv() {
    inv[1] = 1;
    for(int i = 2; i < N; i++) {
        inv[i] = ((-(ll)(MOD / i) * inv[MOD % i]) % MOD + MOD) % MOD;
    }
}

inline void initFi(int k) {
    memset(fi, 0, sizeof(fi));
    tot = 0;
    fi[1] = 1;
    for(int i = 2; i <= k + 1; i++) {
        if(!fi[i]) {
            fi[i] = quickPow(i, k);
            prime[tot++] = i;
            for(int j = 0; i * prime[j] < N; j++) {
                fi[i * prime[j]] = (ll)fi[i] * fi[prime[j]] % MOD;
                if(i % prime[j] == 0) {
                    break;
                }
            }
        }
    }
    for(int i = 2; i <= k + 1; i++) {
        fi[i] = (fi[i] + fi[i - 1]) % MOD;
    }
}

inline void Lagrange(ll n, int k) {
    int p = 1;
    for(int i = 1; i <= k + 1; i++) {
        ans[i] = (i + k + 1) & 1 ? MOD - fi[i] : fi[i];
        p = (ll)p * ((n - i + 1) % MOD) % MOD * inv[i] % MOD;
        ans[i] = (ll)ans[i] * p % MOD;
    }
    p = 1;
    for(int i = k; i >= 1; i--) {
        p = (ll)p * ((n - i - 1) % MOD) % MOD * inv[k + 1 - i] % MOD;
        ans[i] = (ll)ans[i] * p % MOD;
    }
}

int main() {
    initInv();

    int t;
    scanf("%d", &t);
    while(t--) {
        ll n;
        int k;
        scanf("%lld%d", &n, &k);
        initFi(k);
        Lagrange(n, k);
        int res = accumulate(ans, ans + k + 2, 0, [] (int a, int b) -> int { return (a + b) % MOD; });
        printf("%d\n", res);
    }
}