Luogu P4781【模板】拉格朗日插值

​​洛谷传送门​​

板题…注意一下求多个数的乘积的逆元不要一个个快速幂求逆元,那样很慢,时间复杂度就是.直接先乘起来最后求一次逆元就行了.时间复杂度为

这样的拉格朗日插值是预处理,插入,查询的.使用的前提是可以求逆元.

CODE

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template<typename T>void read(T &num) {
    char ch; int flg=1;
    while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;
    for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());
    num*=flg;
}
const int MAXN = 2005;
const int mod = 998244353;
int n, k, x[MAXN], y[MAXN], w[MAXN];
inline int qmul(int a, int b) {
    int res = 1;
    while(b) {
        if(b&1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return res;
}
inline int l(int k) {
    int res = 1;
    for(int i = 0; i < n; ++i)
        res = 1ll * res * (k-x[i]) % mod;
    return res;
}
int main() {
    read(n), read(k);
    for(int i = 0; i < n; ++i)
        read(x[i]), read(y[i]);
    for(int i = 0; i < n; ++i) {
        w[i] = 1;
        for(int j = 0; j < n; ++j)
            if(x[i]-x[j]) w[i] = 1ll * w[i] * (x[i]-x[j]) % mod; //这里先乘起来
        w[i] = 1ll * qmul(w[i], mod-2) * y[i] % mod; //再求逆元
    }
    int Ans = 0;
    for(int i = 0; i < n; ++i) {
        if(k == x[i]) return printf("%d\n", y[i]), 0; //虽然数据保证不会出现k=x[i]的情况,但还是判一下
        Ans = (Ans + 1ll * w[i] * qmul(k-x[i], mod-2) % mod) % mod;
    }
    Ans = 1ll * Ans * l(k) % mod;
    printf("%d\n", (Ans + mod) % mod);
}