有一类数列递推是像卡特兰数一样我卷我自己类型的。
举一个例子：

f0=0,f1=f2=1,fi=∑j=1i−2fjfi−1−jf_0=0,f_1=f_2=1,f_i=\sum_{j=1}^{i-2}f_jf_{i-1-j}

这个怎么分治FFT？我们平常的分治FFT是 f=f*g类型的，做法是cdq分治，到一个区间 [l,r][l,r] 时先算出 [l,mid][l,mid]，再用 f[l,mid]f[l,mid] 和 g[0,r−l]g[0,r-l] 卷起来算出对 [mid+1,r][mid+1,r] 的贡献，再递归右边。
把这里的 gg 直接换成 ff？其实不可以，因为当我们需要用到 [0,r−l][0,r-l] 时有可能它还没算出。
那么考虑换一种思路。之前的“左边对右边的贡献”定义为 ff 的下标属于左边的区间，但是现在式子里有两个 ff，那么我们重新定义为两个下标较大的那个属于左边的区间。
这时就可以计算贡献了。
当区间的 l=0l=0 时，较大的指针属于左边的区间那么较小的也就属于这个区间，只需要自己卷一下再统计贡献即可。
若区间的 l≠0l\neq0，则我们需要考虑它与前面区间的贡献了。一个结论是此时的 r−l<lr-l<l 一定成立。考虑线段树的结构，它的左儿子区间大小只会大于等于右儿子。我们已经向右递归过的话，则左边的大小一定会大于等于右边的大小。于是此时也没有未知的量，直接卷一下统计贡献即可。
复杂度还是 O(nlog2n)O(nlog^2n)。

#include<bits/stdc++.h>
using namespace std;
const int N=8e5+50,mod=998244353;
int r[N],lo[N],rt[N],irt[N],inv[N],n;
int Glim(int n){int z=1;while(z<n)z<<=1;return z;}
void getr(int n){for(int i=1;i<n;i++)r[i]=r[i>>1]>>1^(i&1)<<lo[n];}
int power(int x,int y){
    int z=1;
    for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;
    return z;
}
void init(int n){
    int lim=Glim(n);
    for(int i=2,j=0;i<=lim;i<<=1,j++)lo[i]=j,inv[i]=power(i,mod-2);
    for(int i=1;i<lim;i<<=1){
        int Wn=power(3,(mod-1)/(i*2));
        for(int k=0,w=1;k<i;k++,w=1ll*w*Wn%mod)rt[i+k]=w;
    }
    for(int i=1;i<lim;i++)irt[i]=power(rt[i],mod-2);
}
void NTT(int *a,int n,int op){
    for(int i=0;i<n;i++)if(i>r[i])swap(a[i],a[r[i]]);
    for(int i=1,*w=(op>0?rt:irt);i<n;i<<=1)
        for(int j=0;j<n;j+=i<<1)
            for(int k=0;k<i;k++){
                int x=a[j+k],y=1ll*a[i+j+k]*w[i+k]%mod;
                a[j+k]=(x+y)%mod;a[i+j+k]=(x-y)%mod;
            }
    if(op<0)for(int i=0;i<n;i++)a[i]=1ll*a[i]*inv[n]%mod;
}
int a[N],A[N],B[N];
void cdq(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq(l,mid);
    if(!l){//l*2+1<=r
        int lim=Glim(2*(mid-l)+1);
        for(int i=0;i<lim;i++)A[i]=i+l<=mid?a[i+l]:0;
        getr(lim);NTT(A,lim,1);
        for(int i=0;i<lim;i++)A[i]=1ll*A[i]*A[i]%mod;
        NTT(A,lim,-1);
        for(int i=max(2*l+1,mid+1);i<=r;i++)(a[i]+=A[i-2*l-1])%=mod;
    }
    else{
        int lim=Glim((mid-l)+r-l);
        for(int i=0;i<lim;i++)A[i]=i+l<=mid?a[i+l]:0,B[i]=i<r-l?a[i]:0;
        getr(lim);NTT(A,lim,1);NTT(B,lim,1);
        for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%mod;
        NTT(A,lim,-1);
        for(int i=max(l+1,mid+1);i<=r;i++)a[i]=(a[i]+2ll*A[i-l-1])%mod;
    }
    cdq(mid+1,r);
}
int main(){
    scanf("%d",&n);int st=clock();init(n*2);
    a[1]=1;a[2]=1;cdq(0,n);
    printf("%d %d\n",a[n],clock()-st);
    return 0;
}

这个东西我开始不会分治fft，但却自己想出了牛顿迭代。。
把这个递推写成生成函数的形式：

F=xF2+x+x2F=xF^2+x+x^2

然后移个项就是函数求零点的形式啦，直接牛顿迭代就好了。

#include<bits/stdc++.h>
using namespace std;
const int N=8e5+50,mod=998244353;
int r[N],lo[N],rt[N],irt[N],inv[N];
int Glim(int n){int z=1;while(z<n)z<<=1;return z;}
void getr(int n){for(int i=1;i<n;i++)r[i]=r[i>>1]>>1^(i&1)<<lo[n];}
int power(int x,int y){
    int z=1;
    for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;
    return z;
}
void init(int n){
    int lim=Glim(n);
    for(int i=2,j=0;i<=lim;i<<=1,j++)lo[i]=j,inv[i]=power(i,mod-2);
    for(int i=1;i<lim;i<<=1){
        int Wn=power(3,(mod-1)/(i*2));
        for(int k=0,w=1;k<i;k++,w=1ll*w*Wn%mod)rt[i+k]=w;
    }
    for(int i=1;i<lim;i++)irt[i]=power(rt[i],mod-2);
}
void NTT(int *a,int n,int op){
    for(int i=0;i<n;i++)if(i>r[i])swap(a[i],a[r[i]]);
    for(int i=1,*w=(op>0?rt:irt);i<n;i<<=1)
        for(int j=0;j<n;j+=i<<1)
            for(int k=0;k<i;k++){
                int x=a[j+k],y=1ll*a[i+j+k]*w[i+k]%mod;
                a[j+k]=(x+y)%mod;a[i+j+k]=(x-y)%mod;
            }
    if(op<0)for(int i=0;i<n;i++)a[i]=1ll*a[i]*inv[n]%mod;
}
int c[N],d[N];
void Inv(int *a,int *b,int n){
    if(n==1){b[0]=power(a[0],mod-2);return;}
    int m=n+1>>1,lim=Glim(n+m);Inv(a,b,m);
    for(int i=0;i<lim;i++)c[i]=i<n?a[i]:0,d[i]=i<m?b[i]:0;
    getr(lim);NTT(c,lim,1);NTT(d,lim,1);
    for(int i=0;i<lim;i++)c[i]=1ll*c[i]*d[i]%mod*d[i]%mod;
    NTT(c,lim,-1);for(int i=m;i<n;i++)b[i]=-c[i];
}
int X[N],F[N],A[N],B[N];
void calc(int *a,int n){
    if(n==1)return;
    int m=n+1>>1,lim=Glim(n*2);calc(a,m);
    for(int i=0;i<lim;i++)
        X[i]=i==1,F[i]=i<m?a[i]:0,
        A[i]=i<=m?2*a[i-1]%mod:0;
    A[0]=-1;Inv(A,B,n);
    for(int i=n;i<lim;i++)B[i]=0;
    getr(lim);NTT(X,lim,1);NTT(F,lim,1);NTT(B,lim,1);
    for(int i=0;i<lim;i++)A[i]=(X[i]*(1ll*F[i]*F[i]%mod+X[i]+1)%mod-F[i])*B[i]%mod;
    NTT(A,lim,-1);
    for(int i=m;i<n;i++)a[i]=-A[i];
}
int n,a[N],b[N];
int main(){
    scanf("%d",&n);int st=clock();init((n+1)*2);
    calc(a,n+1);
    printf("%d %d",(a[n]+mod)%mod,clock()-st);
    return 0;
}

直接想到牛迭是因为刚刚做了烷基计数，它是牛顿迭代。式子是这样的：

F(x)=1+xF(x)3+3F(x2)F(x)+2F(x3)6F(x)=1+x\frac{F(x)^3+3F(x^2)F(x)+2F(x^3)}{6}

这个 F(x2)F(x^2) 和 F(x3)F(x^3) 好像很奇怪的样子，牛迭的时候不知道怎么处理。它确实是跟 FF 有关呀，那要把它当做变量？并不，因为我们在 nn 扩展到 2n2n 时，F(x^2) 只用到了 nn 以内的系数，而它们已经准确求出，所以现在 F(x2)F(x^2) 和 F(x3)F(x^3) 已经是完全准确，可以把它们看作常量多项式。正常牛迭就好了。（式子长得很恶心）
所以这种题一般可以转化为生成函数的话真的要试着转一转，因为分治FFT其实还是细节比较多的，（可能我比较菜）

然后烷烃计数（咕了）