题目概述

给出 $g$ 以及 $f(0)=1$ ，求：$f(i)=\sum_{j=1}^{i}f(i-j)g(j)$ 。

解题报告

其实我是想学分治+NTT来着的，结果搜分治FFT就搜到这个了，于是填个坑。

这是个卷积的形式，但是由于 $f$ 和之前有关所以不能直接NTT。

考虑cdq分治，每次通过之前求好的 $f([l,mid])$ ，来算出对 $f([mid+1,r])$ 的贡献，这就可以NTT了：

$$ A(i)=f(i+l)(i\in[0,mid-l]),B(i)=g(i)(i\in[1,r-l])\\ C=A*B,f(i+l)\leftarrow C(i) $$

复杂度是 $O(nlog_2^2n)$ 。其实还可以多项式求逆来做，没了解过……

解题报告

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000,maxt=1<<18,MOD=998244353;

int n,g[maxn+5],f[maxn+5],rev[maxt+5],pw[2][maxt+5],A[maxt+5],B[maxt+5];

inline int Pow(int w,int b) {int s=1;for (;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void Pre(int n){
    for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
    for (int i=2;i<=n;i++) pw[0][i]=Pow(3,(MOD-1)/i),pw[1][i]=Pow(pw[0][i],MOD-2);
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void NTT(int *a,int n,int f){
    for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int k=1;k<n;k<<=1){
        int gn=pw[f<0][k<<1],g=1,x,y;
        for (int i=0;i<n;i+=k<<1,g=1)
            for (int j=0;j<k;j++,g=(LL)g*gn%MOD)
                x=a[i+j],y=(LL)a[i+j+k]*g%MOD,AMOD(a[i+j]=x,y),AMOD(a[i+j+k]=x,MOD-y);
    }if (f<0) for (int inv=Pow(n,MOD-2),i=0;i<n;i++) a[i]=(LL)a[i]*inv%MOD;
}
void Solve(int L,int R){
    if (L==R) return;int mid=L+(R-L>>1);Solve(L,mid);
    int t;for (t=1;t<=R-L;t<<=1);Pre(t);
    for (int i=L;i<=mid;i++) A[i-L]=f[i];for (int i=mid-L+1;i<t;i++) A[i]=0;
    B[0]=0;for (int i=1;i<=R-L;i++) B[i]=g[i];for (int i=R-L+1;i<t;i++) B[i]=0;
    NTT(A,t,1);NTT(B,t,1);for (int i=0;i<t;i++) A[i]=(LL)A[i]*B[i]%MOD;NTT(A,t,-1);
    for (int i=mid+1;i<=R;i++) AMOD(f[i],A[i-L]);Solve(mid+1,R);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);n--;for (int i=1;i<=n;i++) scanf("%d",&g[i]);f[0]=1;Solve(0,n);
    for (int i=0;i<=n;i++) i?(putchar(' '),printf("%d",f[i])):printf("%d",f[i]);puts("");return 0;
}