HZOI2019 超级树 dp

题面：https://www.cnblogs.com/Juve/articles/11207540.html(密码)————————————————>>>

题解：

官方题解：

考虑dp[i][j]表示一棵i-超级树,有j条点不重复的路径的方案数。考虑dp[i]对dp[i+1]的
贡献:枚举左子树和右子树的路径条数l、r,记num=dp[i][l]*dp[i][r],则有
• 什么也不做 dp[i+1][l+r]+=num
• 根自己作为一条新路径 dp[i+1][l+r+1]+=num
• 根连接到左子树(或右子树)的某条路径上 dp[i+1][l+r]+=2*num*(l+r)

• 根连接左子树和右子树的各一条路径 dp[i+1][l+r-1]+=2*num*l*r
• 根连接左子树(或右子树)的两条路径 dp[i+1][l+r-1]+=num*(l*(l-1)+r*(r-1))
边界为dp[1][0]=dp[1][1]=1,答案为dp[k][1]。看起来第二维状态可能有2^k那么
大,但注意到从dp[i]转移到dp[i+1]时,路径的条数最多减少1条,因此第二维
只有k个状态对最终的状态有影响,只dp这些状态即可。复杂度O(k³)。

先不说我有没有看懂，就这个提解来说，虽然我不太懂，但我打出来了

只要注意输出答案时最后取个模，其他时候不用频繁取模，它暴不了

打个广告：DeepinC大佬的题解：https://www.cnblogs.com/hzoi-DeepinC/p/11208439.html

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define MAXK 305
#define ll long long
#define re register
using namespace std;
ll k,mod,dp[MAXK][MAXK];
int main(){
	scanf("%lld%lld",&k,&mod);
	dp[1][0]=dp[1][1]=1;
	for(re ll i=1;i<=k;i++){
		for(re ll j=0;j<=k;j++) dp[i][j]%=mod;
		for(re ll l=0;l<=k;l++)
			for(re ll r=0;r+l<=k;r++){
				re ll num=(dp[i][l]*dp[i][r])%mod;
				dp[i+1][l+r]=dp[i+1][l+r]+num;
				dp[i+1][l+r+1]=dp[i+1][l+r+1]+num;
				dp[i+1][l+r]=dp[i+1][l+r]+2*num*(l+r);
				dp[i+1][l+r-1]=dp[i+1][l+r-1]+2*num*l*r;
				dp[i+1][l+r-1]=dp[i+1][l+r-1]+num*(l*(l-1)+r*(r-1));
			}
	}
	printf("%lld
",dp[k][1]%mod);
	return 0;
}