#165. 拉格朗日插值

题目链接：https://loj.ac/problem/165
拉格朗日插值重心优化

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int maxn = 3010;

int num, x[maxn], y[maxn], w[maxn];

int q_pow(int a, int b){
    int ans = 1;
    while(b > 0){
        if(b & 1){
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1; 
    } 
    return ans;
}

inline int inv(int x){
    return q_pow(x, mod-2);
}

inline void ins(int x0, int y0)
{
    num++;
    x[num] = x0;
    y[num] = y0;
    w[num] = 1;
    for(int i = 1; i <= num-1; i++)
    {
        w[i] = w[i]*(x[i]-x0)%mod;
        w[num] = w[num]*(x0-x[i])%mod;
    }
}

inline int f(int x0)
{
    int g = 1, ans = 0;
    for(int i = 1; i <= num; i++)
    {
        if(x[i] == x0) return y[i];
        g = g*(x0-x[i])%mod;
    }
    for(int i = 1; i <= num; i++)
        ans = (ans + y[i]*inv((x0-x[i])*w[i]))%mod;
    return (g*ans%mod+mod)%mod;
}

signed main()
{
    int n, opt;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> opt;
        if(opt == 1)
        {
            int x, y;
            cin >> x >>y;
            ins(x, y);
        }
        else
        {
            int k;
            cin >> k;
            cout << f(k) << endl;
        }
    }
    return 0;
}