lagrange 插值法模板

对于n次多项式

$\Gamma \left(k\right)=\sum _{i=0}^n{y}_i\prod _{j=0,j\ne i}^n\frac{k-x_j}{x_i-x_j}$Γ(k)=i=0∑n​yi​j=0,j̸​=i∏n​xi​−xj​k−xj​​

const int mod=1e9+7;
template<class T>
T qpow(T x,int k){
    T e=1;
    while(k){
        if(k&1)e=1ll*e*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return e;
}
template<class T>
T lagrange(int n,int x[],int y[],T k){
    T ans=0;
    for(int i=0;i<=n;++i){
        T fz=1,fm=1;//分子分母
        for(int j=0;j<=n;++j){
            if(i==j)continue;
            fm=1ll*fm*(x[i]-x[j])%mod;
            fz=1ll*fz*(k-x[j])%mod;
        }
        ans=(1ll*ans+1ll*y[i]*fz%mod*qpow(fm,mod-2)%mod)%mod;
    }
    return (ans+mod)%mod;
}

在x取值连续时的做法

当 $x_i$xi​​ 的取值都是连续的，可以把上面的算法优化到O(n)复杂度
首先把 $x_i$xi​换成i，新的式子为
$f\left(k\right)=\sum _{i=0}^n{y}_i\prod _{i̸=j}\frac{k-j}{i-j}f\left(k\right)$f(k)=i=0∑n​yi​i̸​=j∏​i−jk−j​f(k)
对于 ${\prod }_{i̸=j}^n\frac{k-j}{i-j}$∏i̸​=jn​i−jk−j​​ 可以优化
对于分子来说，我们维护出关于k的前缀积和后缀积，也就是
$pr{e}_i=\prod _{j=0}^{i-1}k-j$prei​=j=0∏i−1​k−j $su{f}_i=\prod _{j=i+1}^{n}k-j$sufi​=j=i+1∏n​k−j
对于分母来说，观察发现这其实就是阶乘的形式，我们用fac[i]来表示 $i!$i!
那么式子就变成了
$f\left(k\right)=\sum _{i=0}^n{y}_i\frac{pr{e}_i\ast su{f}_i}{fac\left[i\right]\ast fac[N-i]}$f(k)=i=0∑n​yi​fac[i]∗fac[N−i]prei​∗sufi​​​
分母可能会出现符号问题，也就是说，当N - i为奇数时，分母应该取负号

const int mod=1e9+7;
template<class T>
T qpow(T x,int k){
    T e=1;
    while(k){
        if(k&1)e=1ll*e*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return e;
}
int lagrange(int n,int x[],int y[],int k){
    int pre[n+1],suf[n+1],fac[n+1],ans=0;
    fac[0]=pre[0]=suf[n]=1;
    for(int i=1; i<=n; ++i)pre[i]=1ll*(k-x[i-1])*pre[i-1]%mod;
    for(int i=n-1;i>=0;++i)suf[i]=1ll*(k-x[i+1])*suf[i+1]%mod;
    for(int i=1;i<=n;++i)fac[i]=1ll*i*fac[i-1]%mod;
    for(int i=0;i<=n;++i){
        int fz=1ll*pre[i]*suf[i]%mod;//分子分母
        int fm=1ll*fac[i]*fac[n-i]%mod;
        if((n-i)&1)fm=(mod-fm)%mod;
        ans=(1ll*ans+1ll*y[i]*fz%mod*qpow(fm,mod-2)%mod)%mod;
    }
    return (ans+mod)%mod;
}

2019南昌邀请赛B. Polynomial

题目链接
Define $f_{\left(x\right)}=a_0+a_1\times x^1+a_2\times x^2+\dots +a_n\times x^n$f(x)​=a0​+a1​×x1+a2​×x2+…+an​×xn

the number maybe tremendous huge, so take the module of 9999991.

For a polynomial, XH doesn’t know any $a_i$ai​ ​ , but he knows the value of $f_{\left(0\right)},f_{\left(1\right)},f_{\left(2\right)}\dots f_{\left(n\right)}$f(0)​,f(1)​,f(2)​…f(n)​ . He wants to calculate ${\displaystyle \sum _{i=L}^R{f}_{\left(i\right)}}$i=L∑R​f(i)​ mod 9999991.

Input

The first line contains a number $T(1\le T\le 5)$T(1≤T≤5) ——the number of test cases.

For each test case. The first line contains two integers $n(1\le n\le 1000)$n(1≤n≤1000) and $m(1\le m\le 2000)$m(1≤m≤2000).

The second line contains n+1 integers,representing the value of $f_{\left(0\right)},f_{\left(1\right)},f_{\left(2\right)}\dots f_{\left(n\right)}$f(0)​,f(1)​,f(2)​…f(n)​
​
The next mm lines, each line contains two integers L, R.

$(1\le L\le R\le 9999990)$(1≤L≤R≤9999990)

Output

For each test case, output m lines, each line contains one integer, the value of $isplaystyle{\sum }_{i=L}^R{f}_{\left(i\right)}$isplaystyle∑i=LR​f(i)​ mod 9999991.

样例输入

1 
3 2
1 10 49 142
6 7 
95000 100000 

样例输出

2519 
1895570 

题意就是知道(0, $f_0$f0​) , (1, $f_1$f1​) … (n, $f_n$fn​) n+1个点,求 $S\left(k\right)={\sum }_{i=0}^{k}f\left(i\right)$S(k)=∑i=0k​f(i)
由n+1个点可求得 $f(n+1)$f(n+1)
再由 $S\left(k\right)-S(k-1)=f\left(k\right)$S(k)−S(k−1)=f(k)可知， $S\left(k\right)={\sum }_{i=0}^{k}f\left(i\right)$S(k)=∑i=0k​f(i)是n+1次多项式
且我们可以求出这n+2个点，分别是
(0, $f_0$f0​) , (1, $f_0+f_1$f0​+f1​), …, (n, $f_0+f_0+...+f_n$f0​+f0​+...+fn​), (n, $f_0+f_0+...+f_n+f_{n+1})$f0​+f0​+...+fn​+fn+1​)
这样，求出 $S\left(k\right)$S(k) 之后
$S\left(r\right)-S(l-1)$S(r)−S(l−1)即为答案。
代码：

#include<bits/stdc++.h>
using namespace std;
char buf[100000],*L=buf,*R=buf;
#define gc() L==R&&(R=(L=buf)+fread(buf,1,100000,stdin),L==R)?EOF:*L++
template<typename T>
inline void read(T&x) {
    int flag=x=0;
    char ch=gc();
    while (ch<'0'||ch>'9')flag|=ch=='-',ch=gc();
    while (ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-48,ch=gc();
    if(flag)x=-x;
}
#define Init(arr,val) memset(arr,val,sizeof(arr))
const int inf=0x3f3f3f3f,mod=9999991,MAXN=1020;
typedef long long ll;//鬼畜数据，只能全部用ll，不然一个点都过不了，浪费了了我一下午。。。。
template<class T>
T qpow(T x,int k) {
    T e=1;
    while(k) {
        if(k&1)e=1ll*e*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return e%mod;
}
ll fac[MAXN],ffa[MAXN];
//fac是阶乘
//ffa是分母，对于m次询问，都是相同的分母，保存起来，
//因为S(x) 已经确定，分母里的快速幂只需求一次即可，不然坑爹数据一个点也过不了
ll lagrange(ll n,ll x[],ll y[],ll k) {
    ll pre[MAXN],suf[MAXN],ans=0;
    fac[0]=pre[0]=suf[n]=1;
    for(int i=1; i<=n; ++i)pre[i]=1ll*(k-x[i-1])*pre[i-1]%mod;
    for(int i=n-1; i>=0; --i)suf[i]=1ll*(k-x[i+1])*suf[i+1]%mod;
    for(int i=0; i<=n; ++i) {
        ll fz=1ll*pre[i]*suf[i]%mod;
        ans=(1ll*ans+1ll*y[i]*fz%mod*ffa[i]%mod)%mod;
    }
    return (ans+mod)%mod;
}

int main() {
    fac[0]=1;
    for(int i=1; i<MAXN; ++i)fac[i]=1ll*i*fac[i-1]%mod;
    ll n,m,x[MAXN],y[MAXN];
    int t;
    read(t);
    while(t--) {
        read(n),read(m);
        for(int i=0; i<=n; ++i) {
            x[i]=i;
            read(y[i]);
        }
        for(int i=0; i<=n; ++i) {//f(x)
        	ll fm=1ll*fac[i]*fac[n-i]%mod;
         	if((n-i)&1)fm=(mod-fm)%mod;
            ffa[i]=1ll*qpow(fm,mod-2)%mod;
   		}
        y[n+1]=lagrange(n,x,y,n+1);//f(n+1)
        x[n+1]=n+1;
        for(int i=1; i<=n+1; ++i)y[i]+=y[i-1];//前缀和就是S（x）个点的y值
        for(int i=0; i<=n+1; ++i) {//m次查询，分母记录下来，求一次即可
        	ll fm=1ll*fac[i]*fac[n+1-i]%mod;
         	if((n+1-i)&1)fm=(mod-fm)%mod;
            ffa[i]=1ll*qpow(fm,mod-2)%mod;
   		}
        while(m--) {
            ll l,r;
            read(l),read(r);
            printf("%lld\n",(lagrange(n+1,x,y,r)-lagrange(n+1,x,y,l-1)+mod)%mod);
        }
    }
    return 0;
}