「雅礼集训 2018 Day1」树

考虑令 $f_{i,j}$ 表示大小为 $i$ 的树,深度为 $j$ 的方案数。

一般的 DP 合并过程:枚举大小为 $a,b$ 的树,然后把 $b$ 的根接到 $a$ 的根下面。但是这样会算重:打个比方,以 $1$ 为根,儿子为 $2,3$ 的树会被算两次。

不过可以发现,原树的任意一颗子树中,编号最小的点一定为根,编号次小的一定与根相连。这样只需要接入 $b$ 的时候钦定 $b$ 的根是编号次小的点即可。

不取模的答案本地用 __int128_t 或者 double 打表即可。

已经实现:提交记录


「雅礼集训 2018 Day1」仙人掌

考虑一个简单的 DP:令 $f_{i,0/1}$ 表示点 $i$ 是否被父亲的边指向时的子树方案数。这个 DP 可以用分治 NTT 优化。

现在考虑环上的情况,令 $g_{i,0/1,0/1}$ 表示环上第 $i$ 个点,上一个点到其是入边 / 出边,其到下一个点是入边 / 出边时前 $i$ 个点的方案数。只需要对子树的 $f$ 做了前缀和就可以快速转移。

最后合并给环中最上面的点即可,用分治 NTT 加速。

已经实现:提交记录

被新码风整吐了。


「雅礼集训 2018 Day1」图

以路径长度为奇数为例。

考虑前 $i$ 个点中,有 $w_0$ 个奇数白点,$w_1$ 偶数白点,$b_0$ 个奇数黑点,$b_1$ 个偶数黑点:

  • 如果当前点为白点:
    • 路径为奇数:
      $$
      2^{w_0+w_1}\sum_{i=0}^{b_0}[2\mid i]\sum_{j=0}^{b_1}{b_0\choose i}{b_1\choose j}=2^{w_0+w_1+b_0+b_1-1}
      $$

    • 路径为偶数:情况类似。

  • 如果当前点为黑点:情况类似。

这样子的话可以发现,奇数路径和偶数路径的数量是相等的,正因为如此,就没必要将奇数和偶数分别记录了。接着考虑黑白点个数。容易发现上述转移式跟黑白点个数并没有关系。

最后需要注意,奇偶路径数相等,即组合数下标按照奇偶分类后和相等,对 ${n\choose m}$ 中 $n=0$ 的情况是不成立的,在这种情况下只能从偶数转移到奇数,需要单独讨论。

判断 $n=0$ 的情况只需要记录是否存在相应节点即可,注意路径数奇偶性还需要再开一维。时间复杂度 $O(n)$ 。

已经实现:提交记录

分类: 文章

Qiuly

QAQ

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注