P8089 『JROI-5』Color
一棵 \(dep\) 层 \(n\) 个节点的完全二叉树，她希望选择其中一个包含根节点的连通块染色，她想知道有几种不同的染色方案，答案对 \(998244353\) 取模。
标签
计数、树形DP、二进制 trick先看普通树形 DP：
记 \(f_n\) 表示包含根节点的连通块染色不同的染色方案数，易得：
\[f_u = (f_{ls} + 1) \times (f_{rs} + 1)
\]
显然，你可以获得 30pts 的高分。
考虑对于满二叉树的部分分。
打表发现规律：对于 \(n\) 层的满二叉树，染色的方案 \(f_n = (f_{n - 1} + 1)^2\)。
证明
我也不会……由此，我们便可以将一部分的上面 \(dp\) 数组的计算替换为预处理好的值。
观察到，