638 字
3 分钟
NOIP模拟 超级树
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]+=numdp[i+1][l+r+1]+=numdp[i+1][l+r]+=2*num*(l+r)dp[i+1][l+r-1]+=2*num*l*rdp[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]);}