BZOJ 4011 [HNOI2015] 落忆枫音

发布于 2017-06-16  145 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4011

题意:在一个 DAG 上加一条给定的边去,求以 1 为根的树形子图的个数...


有一个显然的结论就是对于一个 DAG,其树形子图的个数为:

$$ans=\prod_{i=2}^{n}deg_i$$

其中\(deg_i\) 记为 i 点的度数

大概意思是对于每个点选择任意一条不同的入边都会有一个新的树形子图生成...

但是这题加了一条边,有什么影响呢?有环,那么如果还是套用上式的话会有一些子图包含了环,这些是多余的。

考虑有哪些情况被考虑多余了,首先环一定是由 x->y 这条边和原图上一条 y->x 的路径组成的,如果我们确定了这两条路径,对于别的点,无论如何选择,都是非法的情况,那么实际上答案是这样的

$$ans=\prod_{i=2}^{n}deg_i-\sum_{S=原图 y->x 一条路径的点集}^{  }                \prod_{i=2\wedge i\notin S}^{n}deg_i$$

记录 f[x] 表示我们需要减掉的那个东西... 显然可以按照拓扑序 dp 求出 

初值\(f_y=\frac{\prod_{i=2}^{n}deg_i}{deg_y}\) 含义大概是只有选择了 x->y 这条边才是非法的这样....

需要处理出逆元,开 long long 代码如下:

 


一个非常弱的准退役OIER