[校内训练19_09_05]ca

题意

对于任意1 ≤k≤N，求有多少个左右区分的恰有k个叶子节点的二叉树，满足对于每个节点要么没有叶子节点要么有两个节点，同时不存在一个叶子节点，使得根到它的路径上有不少于M条向左的边。

答案对998244353取模。

思考

将问题放到平面上考虑。起初在原点，我们考虑树的dfs序，每次向左走一次，得到的向量是(1,1)，否则是(1,-1)。

由于题目要求要么没有叶子节点，要么有两个节点，因此路径不会到第四象限。如果某次路径到达或超过了y=M，那么一定是不合法的。

这样一来，我们就可以进行简单的转移，对每个点统计所有合法的路径个数。

代码

 1 // luogu-judger-enable-o2
 2 #include <cstdio>
 3 #define N_MAX 5000
 4 #define M_MAX 5000
 5 #define MOD 998244353
 6 typedef void vnt;
 7 inline int moc(int x) { return x < MOD ? x : x - MOD; }
 8 inline vnt upc(int & x, int y) { x = moc(x + y); }
 9 int m, n, i, j, f[N_MAX + 1][M_MAX + 1];
10 int main()
11 {
12     scanf("%d %d", &m, &n);
13     f[1][0] = 1;
14     for (i = 1; i < n; ++i)
15         for (j = 0; j < m; ++j)
16         {
17             if (j < m - 1)
18                 upc(f[i][j + 1], f[i][j]);
19             if (j > 0)
20                 upc(f[i + 1][j - 1], f[i][j]);
21         }
22     for (i = 1; i <= n; ++i)
23         printf("%d
", f[i][0]);
24     return 0;
25 }

View Code