显然,两个序列本质不同等价于它们的笛卡尔树不同。而题目这个关于 \(m\) 的限制等价于,每个叶子节点到根路径上,满足“该点是其父亲的左儿子“的节点数不超过 \(m-1\)。
考虑 \(dp\)。\(dp_{m,n}\) 表示有多少个长度为 \(n\) 的序列,满足每个叶子节点到根路径上左儿子个数不超过 \(m-1\),那么有转移 \(dp_{m,n}=\sum\limits_{x=0}^{n-1}dp_{m,x}dp_{m-1,n-1-x}\)。记 \(F_m(x)\) 为 \(dp_{m,n}\) 的 OGF,那么有 \(F_m(x)=F_{m}(x)F_{m-1}(x)+1\),这样可以得到 \(F_m(x)=\dfrac{1}{1-F_{m-1}(x)·x}\)。
一眼连分数化简。考虑将 \(F_m(x)\) 表示为两个 \(m\) 次多项式 \(A_m(x),B_m(x)\) 相除的结果,即设 \(F_m(x)=\dfrac{A_m(x)}{B_m(x)}\)。那么可以得到 \(A_m(x)=B_{m-1}(x),B_{m}=B_{m-1}(x)-A_{m-1}(x)·x\),写成矩阵的形式就是 \(\begin{bmatrix}A_{m-1}(x)&B_{m-1}(x)\end{bmatrix}\times\begin{bmatrix}0&-x\\1&1\end{bmatrix}=\begin{bmatrix}A_{m}(x)&B_{m}(x)\end{bmatrix}\),直接矩阵快速幂是 2log 的,然后发现可以令 \(x\) 为单位根,插完值之后 IDFT 重新得到多项式系数,这样求解 \(A_m(x),B_m(x)\) 就是 1log,然后就是求个逆得到 \(F_m(x)\)。
时间复杂度 \(O(n\log n)\)。
据说有 500B 的做法,没看懂。
const int MAXN=1e5;
const int MAXP=1<<18;
const int pr=3;
const int ipr=332748118;
const int MOD=998244353;
int qpow(int x,int e){int ret=1;for(;e;e>>=1,x=1ll*x*x%MOD)if(e&1)ret=1ll*ret*x%MOD;return ret;}
int rev[MAXP+5];
void NTT(vector<int> &a,int len,int type){
int lg=31-__builtin_clz(len);
for(int i=0;i<len;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<lg-1);
for(int i=0;i<len;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
for(int i=2;i<=len;i<<=1){
int W=qpow((type<0)?ipr:pr,(MOD-1)/i);
for(int j=0;j<len;j+=i){
for(int k=0,w=1;k<(i>>1);k++,w=1ll*w*W%MOD){
int X=a[j+k],Y=1ll*a[(i>>1)+j+k]*w%MOD;
a[j+k]=(X+Y)%MOD;a[(i>>1)+j+k]=(X-Y+MOD)%MOD;
}
}
}
if(!~type){
int iv=qpow(len,MOD-2);
for(int i=0;i<len;i++)a[i]=1ll*a[i]*iv%MOD;
}
}
vector<int>conv(vector<int> a,vector<int> b){
int LEN=1;while(LEN<a.size()+b.size())LEN<<=1;
a.resize(LEN,0);b.resize(LEN,0);NTT(a,LEN,1);NTT(b,LEN,1);
for(int i=0;i<LEN;i++)a[i]=1ll*a[i]*b[i]%MOD;
NTT(a,LEN,-1);return a;
}
vector<int>getinv(vector<int>a,int len){
vector<int>b(len,0);b[0]=qpow(a[0],MOD-2);
for(int i=2;i<=len;i<<=1){
vector<int>c(b.begin(),b.begin()+(i>>1));
vector<int>d(a.begin(),a.begin()+i);
c=conv(c,c);d=conv(c,d);
for(int j=0;j<i;j++)b[j]=(2*b[j]%MOD-d[j]+MOD)%MOD;
}return b;
}
int n,m,LEN=1;
struct mat{
int a[2][2];
mat(){memset(a,0,sizeof(a));}
friend mat operator *(const mat &X,const mat &Y){
mat ret;
for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)
ret.a[i][j]=(ret.a[i][j]+1ll*X.a[i][k]*Y.a[k][j])%MOD;
return ret;
}
};
int main(){
scanf("%d%d",&n,&m);if(m>n)return puts("0"),0;
while(LEN<=n)LEN<<=1;int W=qpow(pr,(MOD-1)/LEN);
vector<int>a(LEN),b(LEN);
for(int i=0,pw=1;i<LEN;i++,pw=1ll*pw*W%MOD){
mat trs,ret;
trs.a[0][1]=MOD-pw;trs.a[1][0]=trs.a[1][1]=1;
ret.a[0][0]=ret.a[1][1]=1;
for(int e=m;e;e>>=1,trs=trs*trs)if(e&1)ret=ret*trs;
a[i]=(ret.a[0][0]+ret.a[1][0])%MOD;
b[i]=(ret.a[0][1]+ret.a[1][1])%MOD;
}
NTT(a,LEN,-1);NTT(b,LEN,-1);
printf("%d\n",conv(a,getinv(b,LEN))[n]);
return 0;
}