Solution P14560 | Make a Happy Morning

· · 题解

首先挂一个 CF1152D 的 \mathcal{O}(n^2) 做法：

最大匹配转最大独立集。

然后用树上最大独立集的经典拆贡献做法。

具体地，令 f_i 表示以 i 为根的子树的最大独立集；令 g_i 表示以 i 为根的子树，要求根节点不选的最大独立集。

令 h_i=f_i-g_i，当 i 的所有儿子的 h_i 均为 0 时，h_i = 1，否则 h_i = 0。

最后的 f_{root} = \sum_{i\in V} h_i，V 是树的点集。

注意到整个大 trie 树上有很多相同结构的子树。令 T_{i,j} 表示深度为 i，到根链上有 j 个多余左括号的一棵树。

对于所有 T_{i,j}，求出其根节点的 h 值是否为 1，再用反射容斥计算它在大 trie 上出现了几次，即可 \mathcal{O}(n^2) 统计答案。

submission

在上述做法的基础上，打表发现 T_{i,j} 的根结点 h 值为 1，当且仅当 i,j 都是奇数。利用这个性质化简式子，就可以得到一个 \mathcal{O}(n) 的答案形式。

答案是 \sum \limits_{i=1}^n \binom{2n-2i+1}{n-i+1}-\binom{2n-2i+1}{n+1}。不难发现前者是可以简单预处理的。

难点在后者：f(n) = \sum \limits_{i=1}^n \binom{2n-2i+1}{n+1} = \sum \limits_{i=0}^{n-1} \binom{2i+1}{n+1}。

考虑利用递推手段求 f(n)。那我们肯定把式子向 f(n-1) 的形式转化。

但是上标跟奇偶性有关。我们引入 g(n) = \sum \limits_{i=0}^{n-1} \binom{2i}{n+1} 试图拼凑。

f(n) = \sum \limits_{i=0}^{n-1} \binom{2i+1}{n+1} = \sum \limits_{i=0}^{n-1} \binom{2i}{n+1} + \binom{2i}{n} = g(n) + g(n-1) + \binom{2n-2}{n}

但是 g(n) 怎么求也成了问题。利用它和 f(n) 的相似性，把它和 f(n) 加起来：

f(n)+g(n)=\sum \limits_{i=0}^{2n-1} \binom{i}{n+1}=\binom{2n}{n+2}

所以就有：

f(n)=(\binom{2n}{n+2}-f(n))+g(n-1)+\binom{2n-2}{n} 2f(n) = \binom{2n}{n+2}+g(n-1)+\binom{2n-2}{n}

至此问题得以 \mathcal{O}(n) 解决。