2019icpc南昌邀请赛B Polynomial （拉格朗日插值法）

题目链接：https://nanti.jisuanke.com/t/40254

题意：

思路：

这题要用到拉格朗日插值法，网上查了一下，找到一份讲得特别好的：

--------------------------------------------------------

以上关于拉格朗日插值法的理论转载自：https://blog.csdn.net/ftx456789/article/details/90750508

关于这道题的做法：
这题给了x从0~n的n+1种取值，那么可以用O(n)来插值，但是它所要求的是。能够想到要用前缀来预处理，我们令：

，则答案为。

直接预处理S(x)肯定会T，我们再用一次拉格朗日插值法。

先知道一个常识：n次多项式的前缀和是 n+1 次的多项式，也就是说 S(x)S(x) 要通过 n+2 个点来求出，然而题目只给出了n+1 个点。我们利用前面的插值法求出f(n+1)，这样就有了n+2个点。之后就可以对S(x) 进行插值了。总复杂度为O(T*m*n)

要注意的是要线性求逆元，如果用费马小定理会T。

AC代码：

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long LL;

const int maxn=;

const int MOD=;

int T,n,m;

LL a[maxn],inv[MOD+],finv[maxn];

LL sum[maxn],ans;

LL qpow(LL a,LL b){

    LL res=;

    while(b){

        if(b&) res=res*a%MOD;

        a=a*a%MOD;

        b>>=;

    }

    return res;

}

void init(){

    inv[]=;

    for(int i=;i<=MOD+;++i)

        inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;

    finv[]=;

    for(int i=;i<=;++i)

        finv[i]=finv[i-]*inv[i]%MOD;

}

LL cal(LL x,LL *a,LL up){

    LL res=;

    LL p=;

    for(LL i=;i<=up;++i)

        p=p*(x-i)%MOD;

    for(LL i=;i<=up;++i){

        int f=(up-i)&?-:;

        res=(res+MOD+a[i]*f*p%MOD*inv[x-i]%MOD*finv[i]%MOD*finv[up-i]%MOD)%MOD;

    }

    return res;

}

int main(){

    init();

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&m);

        for(int i=;i<=n;++i){

            scanf("%lld",&a[i]);

            a[i]%=MOD;

        }

        a[n+]=cal(n+,a,n);

        sum[]=a[];

        for(int i=;i<=n+;++i)

            sum[i]=(sum[i-]+a[i])%MOD;

        while(m--){

            int l,r;

            scanf("%d%d",&l,&r);

            if(r<=n+){

                printf("%lld\n",(sum[r]-sum[l-]+MOD)%MOD);

                continue;

            }

            if(l-<=n+)

                ans=(cal(r,sum,n+)-sum[l-]+MOD)%MOD;

            else

                ans=(cal(r,sum,n+)-cal(l-,sum,n+)+MOD)%MOD;

            printf("%lld\n",ans);

        }

    }

    return ;

}

巴特西

2019icpc南昌邀请赛B Polynomial （拉格朗日插值法）

最新文章

热门文章