拉格朗日插值 2

题目：

给你一个次数不超过 $n$ 的函数 $f(x)$ 在点 $0,1,...n$ 上的取值 $f(0), f(1), \ldots, f(n)$ ，以及一个整数 $m$ ，就 $f(m), f(m+1), \ldots, f(m+n)$ 的值。

答案对 $998244353$ 取模。

题解：

当然这题可以推广成很多题,例如:求 $\sum_{i=1}^{n} i^{k}$ 中的连续的m项。

我们首先要会普通的拉格朗日插值， $f(k)=\sum_{i=1}^{n} y_{i} \prod_{i \neq j} \frac{k-x[j]}{x[i]-x[j]}$

还要会在 $x$ 取值连续时的做法， $f(k)=\sum_{i=1}^{n} y_{i} \frac{p r e_{i-1} * s u f_{i+1}}{jc[i] * jc[n-i]}$

你还要会多项式乘法，由于本题对 $998244353$ 取模，所以用 $ntt$ ，元根是 $3$

前置知识有点多啊啊啊

由于是连续的点 $0-n$ ，即 $x[i]=i$
$ $pre[i]=pre[i-1]*(k-i)$ $

$nxt[i]=nxt[i+1]*(k-i)$ $f(k)=\sum_{i=1}^{n} y_{i} \frac{(\prod_{i=1}^{n}k-i )\times(inv[k-i])}{jc[i] * jc[n-i]}$

我们设 $f(m), f(m+1), \ldots, f(m+n)$ 为多项式 $ans[]$

我们可以先把 $jc[],inv[]$ 等多项式用拉格朗日插值的方法预处理出来，再用 $ntt$ 把这些多项式乘起来得到 $ans[]$

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define int long long
const int mod=998244353;
const int gi=3;
const int N=1e6+5;
int n,m,bit,y[N],jc1[N],jc2[N],inv1[N],inv2[N],f[N],g[N],rev[N];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
#define gc getchar
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
int kuai(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b%2==1)res=res*a%mod;
        a=a*a%mod;
        b=b/2;
    }
    return res;
}
void Pre(int n,int m)
{
    jc1[0]=jc2[0]=1;
    for(int i=1;i<=n;i++)
    {
        jc1[i]=jc1[i-1]*i%mod;
        jc2[i]=jc2[i-1]*(m+i)%mod;
    }
    inv1[n]=kuai(jc1[n],mod-2);
    inv2[n]=kuai(jc2[n],mod-2);
    for(int i=n-1;i>=0;i--)
    {
        inv1[i]=inv1[i+1]*(i+1)%mod;
        inv2[i]=inv2[i+1]*(m+i+1)%mod;
    }
}
void work(int n)
{
    for(int i=1;i<n;i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<bit);
}
void ntt(int *a,int n,int op)
{
    for(int i=1;i<n;i++)
        if(i<rev[i])swap(a[i],a[rev[i]]);
    int w,ii,wn,t;
    for(int i=2,ii=1;i<=n;i*=2,ii*=2)
    {
        wn=kuai(gi,(mod-1)/i);
        for(int j=0;j<n;j+=i)
        {
            w=1;
            for(int k=0;k<ii;k++)
            {
                t=(long long)w*a[j+k+ii]%mod;
                a[j+k+ii]=(a[j+k]-t+mod)%mod;
                a[j+k]=(a[j+k]+t)%mod;
                w=(long long)w*wn%mod;
            }
        }
    }
    if(op==-1)
    {
        reverse(a+1,a+n);
        int inv=kuai(n,mod-2);
        for(int i=0;i<n;i++)a[i]=(long long)a[i]*inv%mod;
    }
}
signed main()
{
    n=read();m=read();
    for(int i=0;i<=n;i++)y[i]=read();
    Pre(n*2,m-n);
    int s=1,len=n*2;
    while(s<=len)
    {
        s=s*2;
        bit++;
    }
    bit--;
    work(s);
    for(int i=0;i<=n;i++)
    {
        f[i]=y[i]*inv1[i]%mod;
        g[i]=((i&1)?mod-1:1)*inv1[i]%mod;
    }
    ntt(f,s,1);
    ntt(g,s,1);
    for(int i=0;i<s;i++)f[i]=f[i]*g[i]%mod;
    ntt(f,s,-1);
    s=s*2;
    bit++;
    work(s);
    for(int i=n+1;i<s;i++)f[i]=0;
    for(int i=0;i<=n*2;i++)g[i]=inv2[i];
    for(int i=n*2+1;i<s;i++)g[i]=0;
    ntt(f,s,1);
    ntt(g,s,1);
    for(int i=0;i<s;i++)f[i]=f[i]*g[i]%mod;
    ntt(f,s,-1);
    for(int i=0;i<=n;i++)printf("%lld ",f[n+i]*jc2[n+i]%mod);
    return 0;
}