AC. 梦想

frank_c1

[ZJOI 2017] 仙人掌

发布于2017年03月25日 | 暂无评论 | 689阅读 | 动态规划,

题意简述

给定nm边的简单无向连通图。

现在要在图上加若干边,要求加边后还是一个简单无向连通图,且每条边至多属于一个简单环。

求加边方案数对998244353取模的值。

1 \le n \le 5 \times 10 ^ 5, 1 \le m \le 10 ^ 6

算法讨论

考后再写一遍的时候发现写的好快啊QAQ

先判一下原图是不是仙人掌。具体可以先DFS一棵生成树,就有许多返祖边,树上差分一下就可以求出每个点连向父亲的边被覆盖了多少次,大于一次就无解。特殊地,等于一次的边就是环边。

首先发现加的边不可能经过某个环。也就是说,环把仙人掌分成若干棵树。树与树之间是相互独立的。所以我们可以对每棵树统计加边方案数再相乘。

问题就转化成在一棵树上加边变成仙人掌的方案数。这个问题还是有点难求。不妨考虑判定仙人掌的过程,每条边至多被覆盖一次。那么连一个环就相当于覆盖一条路径。于是问题等价于树上每条边至多被覆盖一次的路径覆盖方案数。我们发现有个至多的条件很讨厌,什么时候某条边没有被覆盖呢?就是这条边在最终方案中是一条树边。那我们可以把它强行考虑成一个两元环。就可以把问题等价成每条边恰好被覆盖一次的路径覆盖方案数了。

这个问题一看就是DP。设f_ii子树的答案。首先i的所有儿子内部的覆盖方案是相互独立的,于是可以先把儿子的答案先相乘。接下来我们可以发现如果这个点不是根,至多有一个儿子的路径可以经过i继续向上延伸,我们就以这个标准分一下类。

如果没有这样的儿子,那么一定有一些儿子两两配对成一些路径,其余的儿子连到根到就终止了。设i个儿子时的方案数是C_i,考虑枚举配对的儿子对数j,有

C_i = \sum_{2j \le i} {{i \choose 2j} G_j}

G_i就是2i个点两两配对的方案数,推一推可以发现

G_i = \frac{1} {2 ^ i} i! {2i \choose i}

如果有这样的儿子,考虑枚举是哪一个,对系数的贡献是i C_{i-1}

把系数计算出来乘上去就转移完了。整个过程特别小清新,给出题人点个赞!

时间复杂度O(n)