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)

解决。

Solution P14560 | Make a Happy Morning

文章操作

相关推荐

评论

Solution P14560 | Make a Happy Morning