本文共 1536 字，大约阅读时间需要 5 分钟。

$f(n)$ 表示叶子节点为 $n$ 的方案数。则根据定义：

如果让 $i$ 枚举 $1$ 到 $n$ ，新的和就变成了 $f(n)$ 的两倍少中间那一点的样子。

于是考虑两边同时 $\times 2$ 把限制放松

左边的和式就是分治fft可做，（注意是自己卷自己和分治fft的模板不太一样。$O(n{\log }^{2}n)$ 。

右边的和式在分治到单个节点的时候暴力算，$O(nk)$ 。

时间复杂度 $O(n{\log }^{2}n+nk)$ 。

#include 
   
    #define N 2000006using namespace std;typedef long long ll; typedef vector
    
      vec;const ll mod=998244353;int now_limit;int rev[N];ll wq[20][N],fac[N],inv[N];ll ksm(ll x,ll y){   	ll res=1; while(y){    if(y&1)res=res*x%mod; x=x*x%mod; y>>=1; }	return res;}void init_NTT(int limit){   	if(limit==now_limit) return;	now_limit=limit; int l=0; while((1<
     
      
       >1]>>1)|((i&1)<<(l-1));	if(wq[0][0]==0){   		while(limit<1000000) limit<<=1;		for(int mid=1,l=0;mid
       
        <<=1,l++){   			wq[l][0]=1,wq[l][1]=ksm(3,(mod-1)/(mid<<1));			for(int k=2;k
        
         k) for(int i=(l-k+1)/2;i+i
         
          >1; cdq_NTT(l,mid); vec a,b; a=vector
          
           (&f[l],&f[mid]); b=vector
           
            (&f[0],&f[min(r-l,mid)]); int limit=1; while(limit
            
             >n>>k; f.resize(n+1); f[1]=2; inv2=ksm(2,mod-2); cdq_NTT(0,n+1); cout<
             
              <<'\n';}