重心拉格朗日插值法

例题:Loj165

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int MOD = 998244353;
const int MAXN = 5000 + 10;
inline int qpow(int64 b, int p, int mod) 
{
    int res = 1;
    while (p) {
        if (p & 1)
            res = res * b % mod;
        b = b * b % mod;
        p >>= 1;
    }
    return res;
}
#define inv(x) qpow(x, MOD - 2, MOD)

int n;
int x[MAXN], y[MAXN], p[MAXN];
int top;
inline void ins(int x0, int y0) 
{
    int i;
    top++;//top最初值为0 
    x[top] = x0;
    y[top] = y0;
    p[top] = 1;
    for (i = 1; i < top; i++) 
	{
        p[i] = 1ll * p[i] * inv(MOD + x[i] - x0) % MOD;
		//第i项的分母 ,因为新增加了一项，所以要多乘一个x[i]-x0 
        p[top] = 1ll * p[top] * (MOD + x0 - x[i]) % MOD;
		//求和时最后一项的分母 
    }
    p[top] = 1ll * inv(p[top]) * y0 % MOD;
}
inline int f(int x0) 
{
    int g = 1, i, sum = 0;
    for (i = 1; i <= top; i++) 
	{
        if (x[i] == x0)
            return y[i];
        g = 1ll * g * (MOD + x0 - x[i]) % MOD;
        //公式中的g 
    }
    for (i = 1; i <= top; i++) 
	sum = (sum + 1ll * p[i] * inv(MOD + x0 - x[i])) % MOD;
	//在算g的时候，每一项都多乘了一项(x0-x[i]),现在再除掉 
    return 1ll * g * sum % MOD;
}

int main() {
    int i, j;
    int opt, x0, y0;
    scanf("%d", &n);
    for (i = 1; i <= n; i++) 
	{
        scanf("%d %d", &opt, &x0);
        x0 %= MOD;
        if (opt == 1) 
		{
            scanf("%d", &y0);
            y0 %= MOD;
            ins(x0, y0);
        } 
		else
            printf("%d
", f(x0));
    }
    return 0;
}