非自身卷积

$f_i=\sum_{k=0}^{i-1}f_kg_{i-k}$ ，$f_0$ 已知，给出 $g_{1..n}$ 。（ $k>i$ 同理）

cdq分治，先处理 $[L,mid]$ 的 $f$ ，然后用 $[L,mid]$ 的 $f$ 更新 $[mid+1,R]$ 的 $f$ 。

$p_i=f_{i+L}(0\le i\le mid-L)$ ，$q_i=g_i(1\le i\le R-L)$ 。

$f_i(mid+1\le i\le R)$ 加上 $[x^{i-L}](p*q)(x)$ 。

卡常技巧：虽然我们要做 $mid-L$ 和 $R-L$ 的卷积，但由于我们只需要用到 $(p*q)(x)$ 从 $mid+1-L$ 开始的部分，因此我们可以将FFT长度设成 $R-L$ ，FFT会循环溢出，但是只会溢出 $mid-L$ ，不会影响到 $mid+1-L$ 后面的部分。

void cdqNTT(int L,int R){
    if (L==R) {/*Update here*/ return;}
    int mid=L+(R-L>>1);
    cdqNTT(L,mid);
    int t;for (t=1;t<=R-L;t<<=1);
    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]=MUL(A[i],B[i]);
    NTT(A,t,-1);for (int i=mid+1;i<=R;i++) f[i]=ADD(f[i],A[i-L]);
    cdqNTT(mid+1,R);
}

自身卷积

$f_i=\sum_{k=1}^{i-1}f_kf_{i-k}(i\ge 2)$ ，$f_0,f_1$ 已知。

还是考虑cdq分治，但是会出现一个问题，在统计 $[L,mid]$ 对 $[mid+1,R]$ 的贡献时，$f_{R-L}$ 可能是未知的（即 $R-L>mid$ ）。

我们先只统计 $[L,mid]$ 中的贡献，即 $[L,mid]$ 卷 $[L,mid]$ ，剩下的贡献在后面补上。

当 $R-L<L$ 时，$[1,R-L]$ 的信息和 $[L,mid]$ 没有重叠，并且 $[1,L-1]$ 的 $f$ 已经求出，因此将 $[1,R-L]$ 和 $[L,mid]$ 卷积，加到 $[mid+1,R]$ 上，从而补上没算的权值。

注意 $k\le R-L,i-k\le R-L$ 在 $[L,mid]$ 卷 $[L,mid]$ 均没有出现，因此需要算两次。

下面以某个式子为例（没错就是青蕈领主但我看不懂题解所以摆烂了）：

$$ f_0=1,f_1=2,f_i=(i-1)f_{i-1}+\sum_{k=2}^{i-2}(k-1)f_kf_{i-k} $$

void Solve(int L,int R){
    if (L==R) {f[L]=ADD(f[L],MUL(L-1,f[L-1]));return;}
    int mid=L+(R-L>>1);
    Solve(L,mid);
    if (R-L<L){
        int t;for (t=1;t<=R-L;t<<=1);
        for (int i=L;i<=mid;i++) A[i-L]=f[i];
        for (int i=mid-L+1;i<t;i++) A[i]=0;
        for (int i=2;i<=R-L;i++) B[i]=MUL(i-1,f[i]);
        B[0]=B[1]=0;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]=MUL(A[i],B[i]);NTT(A,t,-1);
        for (int i=mid+1;i<=R;i++) f[i]=ADD(f[i],A[i-L]);

        for (int i=L;i<=mid;i++) A[i-L]=MUL(i-1,f[i]);
        for (int i=mid-L+1;i<t;i++) A[i]=0;
        for (int i=2;i<=R-L;i++) B[i]=f[i];
        B[0]=B[1]=0;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]=MUL(A[i],B[i]);NTT(A,t,-1);
        for (int i=mid+1;i<=R;i++) f[i]=ADD(f[i],A[i-L]);
    } else {
        int t;for (t=1;t<=(mid-L<<1);t<<=1);
        for (int i=L;i<=mid;i++) A[i-L]=f[i],B[i-L]=MUL(i-1,f[i]);
        for (int i=mid-L+1;i<t;i++) A[i]=B[i]=0;
        NTT(A,t,1);NTT(B,t,1);
        for (int i=0;i<t;i++) A[i]=MUL(A[i],B[i]);NTT(A,t,-1);
        for (int i=mid+1;i<=R;i++) if (i>=(L<<1)) f[i]=ADD(f[i],A[i-(L<<1)]);
    }
    Solve(mid+1,R);
}

f[0]=1;f[1]=2;Solve(2,n);