HZOI2019 超级树 dp

概述题面：https://www.cnblogs.com/Juve/articles/11209454.html(密码)————————————————>>> 题解： 官方题解： 考虑dp[i][j]表示一棵i-超级树,有j条点不重复的路径的方案数。考虑dp[i]对dp[i+1]的 贡献:枚举左子树和右子树的路径条数l、r,记num=dp[i][l]*dp[i][r],则有 • 什么也不做 dp[i+

题面：https://www.cnblogs.com/Juve/articles/11209454.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 registerusing 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\n",dp[k][1]%mod);	return 0;}

总结

以上是内存溢出为你收集整理的HZOI2019 超级树 dp全部内容，希望文章能够帮你解决HZOI2019 超级树 dp所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。