【WC2017四校联考3】优美的树 题解

题目大意

  众所周知，树是n 个节点n-1 条边的结构，而所谓的优美的树需要满足如下条件：
  1. 这是一棵有根二叉树；
  2. 非叶节点需有两个儿子；
  3. 不可以变换为k-左偏树。
  所谓的k-左偏树是指一棵有k 个叶子的树，每个非叶节点的右儿子均为叶子且均有左儿子。
  所谓的变换指的是经过若干次如下两种变换：
  1. 删去一个节点的两个儿子；
  2. 用一个节点的某个儿子替换该节点。
  如下图，若k=3 则这不是一棵优美的树。

  现在给你k 和n，想要你求出叶子数为1,2,3…n 的优美的树分别有多少。
  n,k<=5000

【30%】n,k<=500

  设 $f[i][j]$ 表示有 n 叶子节点、向左深度最大为 j 的这种形态的树的数量。
  转移就是枚举两棵树合并。
  卡下常数好像能70分。

【100%】

  首先去掉那 n+1 个叶子节点，这样就去掉了每个节点一定要有两个儿子的限制。（woc我怎么就想不到）
  按先序遍历的顺序来dp。（woc我怎么就想不到×2）
  设 $f[i][j]$ 表示先序遍历到了第 i 个节点，从 1 到 i 的向左深度为 j，的方案数。转移就是枚举下一个点放哪，可以放自己的左儿子，也可以放祖先（包括）的右儿子。
  有多少祖先缺右儿子呢？其实，我们向左走了 j 步，就相当于有 j 个祖先缺右儿子。（woc我怎么就想不到×3）

代码

#include<cstdio>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=5005;
const LL mo=1e9+9;

int n,k;

LL f[maxn][maxn],g[maxn][maxn];
int main()
{
	scanf("%d %d",&k,&n);
	n--;
	k-=2;
	
	g[0][0]=1;
	fo(i,1,n)
	{
		fo(j,1,k) f[i][j]=g[i-1][j-1];
		fd(j,k,0) g[i][j]=(g[i][j+1]+f[i][j])%mo;
	}
	
	printf("1\n");
	fo(i,1,n) printf("%lld\n",g[i][1]);
}