3.1 描述
一棵k-超级树可按如下方法得到：取一棵深度为k的满二叉树，对每个节
点，向它的所有祖先连边（如果这条边不存在的话）。例如，下图是一个4-超
级树的例子：
现在你的任务是统计一棵k-超级树中有多少条每个节点最多经过一次的不
同有向路径。两条路径被认为不同，当且仅当它们经过的节点的集合不同，或
经过的节点的顺序不同。由于答案可能很大，请输出总路径数对mod取模后的
结果。
3.2 输入
一行两个整数k、mod，意义见上。
3.3 输出
一行一个整数，代表答案
样例
| 输入 | 输出 |
|---|---|
| 2 100 | 9 |
| 3 1000 | 245 |
| 20 998244353 | 450500168 |
样例解释：对第一组样例，将节点如图编号，共有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]);
}