题意
有一颗二叉树，满足一个结点要么是叶子结点，要么有两个儿子。同时，不存在一个叶子结点，使得它到根的路径上经过了 \(\ge m\) 条向左的边。（左右子树有区别）
对于 \(1\le k \le n\)，求满足上述条件，且有 \(k\) 个叶子结点的二叉树，有多少个（\(\bmod~998244353\)）
\(n,m\le 5000\)
思路
众所周知，一个有 \(k\) 个叶子结点的二叉树，其实就是有 \(2k-1\) 个结点。
因为一个非叶结点一定有两个儿子，那么我们可以将这个二叉树看成一个括号序列：
我们按照 dfs 序遍历整个二叉树，向左走就记录一个左括号，向右走就记录一个右括号。
那么一个合法二叉树就对应一个合法括号序列，长度为 \(2k-2\)。
如果我们将左括号看为 \(1\)，右括号看为 \(-1\)，对得到的括号序列求前缀和，那么一定是满足以下条件：
-
任意时刻和 \(\ge 0\)
-
最大的前缀和 \(< m\)
这样，我们就可以用 DP 来做了。
我们设 \(f_{i,j}\) 表示括号序列长度为 \(i\)，前缀和为 \(j\) 的方案数。
转移显然有：
\[f_{i,j}=f_{i-1,j-1}+f_{i-1,j+1} \]代码
#include<bits/stdc++.h>
#define LL long long
#define max(x...) std::max({x})
#define min(x...) std::min({x})
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
inline int rd()
{
int sign = 1, re = 0; char c = getchar();
while(!isdigit(c)){if(c == '-') sign = -1; c = getchar();}
while(isdigit(c)){re = re * 10 + (c - '0'); c = getchar();}
return sign * re;
}
namespace MOD
{
const int mod = 998244353;
inline int add(int a, int b) {return a + b >= mod ? a + b - mod : a + b;}
inline int mul(int a, int b) {return 1ll * a * b % mod;}
inline int sub(int a, int b) {return a - b < 0 ? a - b + mod : a - b;}
} using namespace MOD;
int n, m;
int f[10005][5005];
signed main()
{
#ifdef ONLINE_JUDGE
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
#endif
m = rd() - 1, n = rd();
f[1][0] = 1, puts("1");
FOR(i, 2, (n << 1) - 1)
{
FOR(j, 0, m)
{
if(j < m) f[i][j] = add(f[i][j], f[i - 1][j + 1]);
if(j > 0) f[i][j] = add(f[i][j], f[i - 1][j - 1]);
}
if(i & 1) printf("%d\n", f[i][0]);
}
return 0;
}