3.1 描述#

一棵k-超级树可按如下方法得到：取一棵深度为k的满二叉树，对每个节 点，向它的所有祖先连边（如果这条边不存在的话）。例如，下图是一个4-超 级树的例子：

现在你的任务是统计一棵k-超级树中有多少条每个节点最多经过一次的不 同有向路径。两条路径被认为不同，当且仅当它们经过的节点的集合不同，或 经过的节点的顺序不同。由于答案可能很大，请输出总路径数对mod取模后的 结果。

3.2 输入#

一行两个整数k、mod，意义见上。

3.3 输出#

一行一个整数，代表答案

样例#

样例解释：对第一组样例，将节点如图编号，共有9条不同的路径：1, 2, 3, 1− 2, 2 − 1, 1 − 3, 3 − 1, 2 − 1 − 3, 3 − 1 − 2。

限制与约定#

对于10%的数据，k ≤ 4。 对于40%的数据，k ≤ 10。 对于60%的数据，k ≤ 100。 另有10%的数据，mod = 998244353。 对于所有数据，1 ≤ k ≤ 300，1 ≤ mod ≤ 109。

题解#

考虑dp[i][j]表示一棵i-超级树，有j条点不重复的路径的方案数。 对于第二维表示有j条路径他们不相交的方案数 这记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]

因为我们发现每次转移的时候j最多会减1
所以我们只需要前k-i+1个状态
只DP这些状态就可以了

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long f[305][305];
int MOD;
int main()
{
	int k;
	scanf("%d%d", &k, &MOD);
	f[1][0] = f[1][1] = 1 % MOD;
	for (int i = 1; i < k; i++)
	{
		for (int l = 0; l <= k - i + 1; l++)
			for (int r = 0; r <= k - i + 1; r++)
			{
				long long num = f[i][l] * f[i][r] % MOD;
				if (r + l <= k - i)
				{
					f[i + 1][r + l] = (f[i + 1][r + l] + num) % MOD;
					f[i + 1][r + l] = (f[i + 1][r + l] + 2 * num * (l + r) % MOD) % MOD;
				}
				if (r + l + 1 <= k - i)
					f[i + 1][r + l + 1] = (f[i + 1][r + l + 1] + num) % MOD;
				if (r + l - 1 <= k - i)
				{
					f[i + 1][r + l - 1] = (f[i + 1][r + l - 1] + 2 * num * l * r % MOD) % MOD;
					f[i + 1][r + l - 1] = (f[i + 1][r + l - 1] + num * (l * (l - 1) + r * (r - 1)) % MOD) % MOD;
				}
			}
	}
	printf("%lld", f[k][1]);
}