好杂题

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\) 数组的计算替换为预处理好的值。

观察到，