卡一点细节。

Solution

CDQ 有两种递归方式，就是如果右的答案需要从左获得，那可以是递归解决左，后解决中，再递归解决右的方式。这样可以保证每次递归到 $l=r$ 时 $l$ 的贡献被完全计算。

FFT 也可以是这种方式。对于本题有 $f_j=\sum \limits_{i=l}^{mid}f_ig_{j-i}$，每次我们可以将 $f$ 数组左移来使临时 FFT 的数组变得容易处理，左移后变成：$f_{j-l}=\sum \limits_{i=0}^{mid-l}f_ig_{j-i}$，因此像这样子来做 FFT 然后对右面计算额外的贡献就行了。

同时注意不能将 $f$ 的 $(mid, r]$ 的部分参与到 FFT 的计算中。

Code

// Code by ajcxsu
// Problem: cdqpoly

#include<bits/stdc++.h>
#define MOD (998244353)
using namespace std;

const int N=4e5+10;
int g[N], f[N], x[N], y[N], n, r[N], l;

int qpow(int x, int y, int mo) {
    int ret=1;
    while(y) {
        if(y&1) ret=1ll*ret*x%mo;
        x=1ll*x*x%mo, y>>=1;
    } return ret;
}

void dft(int x[], int d, int n) {
    for(int i=1;i<n;i++) if(i>r[i]) swap(x[i], x[r[i]]);
    int t, w, o;
    for(int i=1;i<n;i<<=1) {
        o=qpow(3, d*(MOD-1)/(i<<1)+MOD-1, MOD);
        for(int j=0;j<n;j+=(i<<1)) {
            w=1;
            for(int k=0; k<i; k++, w=1ll*w*o%MOD)
                t=1ll*x[i+j+k]*w%MOD, x[i+j+k]=(x[j+k]-t+MOD)%MOD,
                (x[j+k]+=t)%=MOD;
        }
    }
}

void mul(int a[], int b[], int m) {
    dft(a, 1, n), dft(b, 1, n); for(int i=0;i<n;i++) a[i]=1ll*a[i]*b[i]%MOD;
    dft(a, -1, n); int inv=qpow(n, MOD-2, MOD); for(int i=0;i<=m;i++) a[i]=1ll*a[i]*inv%MOD;
}

void solve(int l, int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    solve(l, mid);
    ::l=0; for(n=1; n<=2*(r-l+1); n<<=1) ::l++;
    for(int i=1;i<n;i++) ::r[i]=(::r[i>>1]>>1)|((i&1)<<(::l-1));
    fill(x, x+n, 0), fill(y, y+n, 0);
    copy(f+l, f+mid+1, x);
    copy(g, g+r-l+1, y);
    mul(x, y, r-l+1);
    for(int i=mid+1;i<=r;i++) f[i]=(f[i]+x[i-l])%MOD;
    solve(mid+1, r);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin>>n;
    f[0]=1;
    for(int i=1;i<n;i++) cin>>g[i];
    solve(0, n-1);
    for(int i=0;i<n;i++) cout<<f[i]<<" \n"[i==n-1];
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-4721.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆