[P4721] 分治 FFT

「题意」给定\(g[0]=1\),\(g[1~n-1]\)求序列\(f[i]=\sum_{j=1}^i f[i-j]*g[j]\ , i\in[1,n-1],f[0]=1\)。
「分析」分治处理区间[l,r]，先递归求出[l,mid]，在统计[l,mid]对[mid+1,r]的贡献，可以发现
\[f[x]+=\sum_{i=l}^{mid}f[i]*g[x-i]\ , x\in[mid+1,r]\]

拿卷积算，令\(a[0,mid-l]\)=\(f[l,mid]\), \(b[l,r-l]\)=\(g[1,r-l]\) ,\(b[0]=0\)，设\(c[i]\)=\(a[i]*b[i-j]\), 那么
\[f[x]+=\sum f[i]*g[x-1]=\sum a[i-l]*b[x-i]=c[x-l]\]

套上ntt

「代码」

#include <bits/stdc++.h>
using namespace std;
const int n=4e5+10;
const int p=998244353,g=3;

int n,lmt,l,rev[n];
int g[n],f[n],a[n],b[n];

int qpow(int x,int y) {
    int c=1;
    for(; y; y>>=1,x=1ll*x*x%p)
        if(y&1) c=1ll*c*x%p;
    return c;
}
void init(int len) {
    for(lmt=1,l=0; lmt<len+len; lmt<<=1) l++;
    for(int i=0; i<lmt; ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
}
void numbertheoretictransform(int a[n],int tp) {
    for(int i=0; i<lmt; ++i) if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int m=1; m<lmt; m<<=1) {
        long long wm=qpow(g,(p-1)/(m<<1));
        if(tp==-1) wm=qpow(wm,p-2);
        for(int i=0; i<lmt; i+=(m<<1)) {
            long long w=1,tmp;
            for(int j=0; j<m; ++j,w=w*wm%p) {
                tmp=w*a[i+j+m]%p;
                a[i+j+m]=(a[i+j]-tmp+p)%p;
                a[i+j]=(a[i+j]+tmp)%p;
            }
        }
    }
    if(tp==-1) {
        long long tmp=qpow(lmt,p-2);
        for(int i=0; i<lmt; ++i) a[i]=tmp*a[i]%p;
    }
}
void dfs(int l,int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    dfs(l,mid);
    init(r-l+1);
    for(int i=0; i<lmt; ++i) a[i]=b[i]=0;
    for(int i=l; i<=mid; ++i) a[i-l]=f[i];
    for(int i=0; i<=r-l; ++i) b[i]=g[i];
    numbertheoretictransform(a,1);
    numbertheoretictransform(b,1);
    for(int i=0; i<lmt; ++i) a[i]=1ll*a[i]*b[i]%p;
    numbertheoretictransform(a,-1);
    for(int i=mid+1; i<=r; ++i) f[i]=(f[i]+a[i-l])%p;
    dfs(mid+1,r);
}


int main() {
    scanf("%d",&n);
    for(int i=1; i<n; ++i) scanf("%d",g+i);
    f[0]=1, dfs(0,n-1);
    for(int i=0; i<n; ++i) printf("%d ",f[i]);
    printf("\n");
    return 0;
}

ubuntu的中括号怎么是这个鬼玩意儿//