C++拉格朗日插值法

Question

洛谷原题：https://www.luogu.com.cn/problem/P4781
有几个问题，第28行为什么需要pow(P-2,b)%P？b不是作为拉格朗日插值法基函数的分母吗，这么写的意义是什么？
以及该如何修改才能通过样例？修改了一晚上无果，谢谢。

我的代码（改题解的代码改的）：

#include<cstdio>
#include<iostream>
#include<algorithm>
#define P 998244353
using namespace std;

int n,k;
int a,b,ans;
int x[2005],y[2005];

int pow(int k,int n){
    int r=1;
    for(;k;k>>=1,n=n*n%P)if(k&1)r=r*n%P;
    return r;
}

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++){
        a=y[i]%P ;
        b=1;
        for(int j=1;j<=n;j++){
            if(i==j)continue;
            a=a*(k-x[j])%P;
            b=b*(x[i]-x[j])%P;
        }
        ans=(ans+a*pow(P-2,b)%P)%P;
    }
    cout<<(ans+P)%P;
    return 0;
}

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7497625

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^