【17 提高 1】 给

【17 提高 1】 给

背景描述

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

你只需要求出答案对 998244353 取模的结果。

输入格式

输入共一行，两个正整数 m, n。

输出格式

输出 n 行每行一个整数， 第 i 行输出恰有 i 个叶子节点的时候的答案对 998244353 取模的结果。

样例输入

3 5

样例输出

1

1

2

4

8

数据规模和约定

对于 20% 的数据， n,m≤8

对于 35% 的数据， n,m≤300

对于 60% 的数据， n,m≤1500

对于 100% 的数据， 1≤n,m,≤5000

题目信息

题目类型：传统型

输入文件：标准输入

输出文件：标准输出

时间限制：1 s

空间限制：512 MB

样例解释

样例一：

样例二

样例三

共两种

样例四：

共四种

性质

1.图是可以一步步附加上去的（根据叶子节点的个数在原来的方案上继续添加节点，每一个状态都可以从上一个状态转移过来），可以用树形DP。

2.在前一个图上加新的叶子节点一次必须加两个，不能只加一个，没加一次都要注意有没有超过m 条向左的边。

由此，我们可以设置dp[ i ] [ j ]，表示叶子节点个数为i个时，向左的边最大个数为j的方案数。

这道题如果要暴力的话也是要考虑树的形状，那么理所当然就能想到DP，所以暴力的想法被舍弃了。

DP

1.顺着原先方案的一边下去

f[i + 1] [j + 1] = (f[i + 1] [j + 1] + f[ i ] [ j ]) % mod;

2.左右调换

f[i] [j - 1] = (f[i] [j - 1] + f[i] [j]) % mod

思路总结

我们先是看出了这是DP，然后确立了DP的数组，我们需要维护什么就设什么数组f[i] [j],表示叶子节点个数为i个时，向左的边最大个数为j的方案数。 （需要维护叶子节点个数，向左的最大边数）

对于每种状态如何转移，用集合的思想去分析，也是这道题最难的地方。

首先这道题与其他的常见题目不同，它有左右的区分，状态转移方程1是容易想的，方程2则不容易想到。我们一般用集合法去分析，往往都是由后到前，但这样想适合多(前一个状态）对一（后一个状态）的情况，但在本题中，我们要用f[i] [j]去想f[i + 1] [j + 1]，又要用f[i] [j]去想f[i] [j - 1]。属于一（前一个状态）对多（后一个状态）。由此可见考虑集合法要完整慎重。

DP最关键的地方在于对自己要维护的东西有清楚的认知，什么时候都不能丢，才能确立完整正确的状态转移方程，难怪有人说DP是优雅的暴力。

注意事项

状态转移时，注意数据不能提前更新，避免转移发生冲突。

代码

#include
using namespace std;
const int mod=998244353;
const int maxn=5005;
const int maxm=5005;
int add(int x)
{
	return x >= mod ? x - mod : x;
}
int m,n;
int f[maxn][maxm];
void dp()
{
	f[1][1]=1;
	for(int i=1;i<=n;++i)
	{
		int lim=min(i,m);
		for(int j=lim;j>=1;--j)//防止更新顺序混乱（覆盖）。
		{
			f[i][j-1]=add(f[i][j-1]+f[i][j]);
			f[i+1][j+1]=add(f[i+1][j+1]+f[i][j]);
		}
	}
}
int main()
{
	scanf("%d%d",&m,&n);
	dp();
	for(int i=1;i<=n;++i)
	{
		printf("%d\n",f[i][1]);
	}
	return 0;
}