NOI2015冬令营陈立杰《计数》.pdf

《NOI2015冬令营陈立杰《计数》.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计数问题选讲陈立杰清华大学交叉信息学院February9,2015........................................陈立杰(清华大学交叉信息学院)计数问题选讲February9,20151/67intro.￿￿￿￿￿￿￿￿￿￿￿￿........................................陈立杰(清华大学交叉信息学院)计数问题选讲February9,20152/67TableofContents1Part1.有趣的容斥原理2Part2.dp套dp3Part3.有技巧的枚举(分类)4Part4.期望的线性性..........

2、..............................陈立杰(清华大学交叉信息学院)计数问题选讲February9,20153/67Part1.有趣的容斥原理大家应该都知道容斥原理吧。好了，我们已经知道这个模型是怎么回事了，让我们看几道题目来学习一下吧！........................................陈立杰(清华大学交叉信息学院)计数问题选讲February9,20154/67Biconnected给你一个n(n10)个点的无向简单图，问有多少个边的子集E′E,使得只保留E′中的边的话，整个图是双联通的。也就是问你有多少个关于边的子

3、图（点集合还是这n个点）双连通。2014ACM/ICPCAsiaRegionalAnshanOnline,byme.........................................陈立杰(清华大学交叉信息学院)计数问题选讲February9,20155/67做法1直接处理这个问题并不容易，不妨考虑如何计算使得整个图不双联通的边集。注意到一个不双联通的图，必然能够唯一地分成几个双联通块，并且这些块之间组成了一棵森林。........................................陈立杰(清华大学交叉信息学院)计数问题选讲February9,20

4、156/67做法1cont.那么我们不妨先枚举这个图如何被划分成了几个联通块，然后计算这些联通块之间连成森林的方法数即可。每个联通块连成双联通图的方案数就是一个子问题了，集合dp计算即可。后者是一个经典问题，我们先枚举森林中哪些点组成了树，然后使用生成树数量的计数公式即可。复杂度比较高，所以只能处理n10。........................................陈立杰(清华大学交叉信息学院)计数问题选讲February9,20157/67做法2abs.使用和下面一个题目类似的方法可以做到n15。..........................

5、..............陈立杰(清华大学交叉信息学院)计数问题选讲February9,20158/67sconnect给你一个n(n15)个点的有向简单图，问有多少个边的子集E′E,使得只保留E′中的边的话，整个图还是强连通的。2014TsinghuaTrainingCamp,byme.........................................陈立杰(清华大学交叉信息学院)计数问题选讲February9,20159/67做法1还是非常难直接处理这个问题，和上一题类似，我们来考虑如何非强连通的子图数量。相信聪明的同学立马就发现了，非强联通的图当然

6、就是一些强连通分量组成的DAG啦。那么我们立刻有了简单粗暴的做法1，枚举分成强联通分量的划分方案，对于每一个划分计算连成DAG的方案数。........................................陈立杰(清华大学交叉信息学院)计数问题选讲February9,201510/67做法1计算DAG那么我们现在需要考虑这个问题，给你n个点的图，计算有多少子图是DAG。这个问题也是一个非常经典的问题，我们可以采用集合dp，令D[S]表示S这个集合有多少子图是DAG，我们知道一个DAG就会有一些没有出度的汇点，那么我们枚举S中汇的集合T，不能保证SnT中就没有汇，可

7、能出现重复计算。所以可以使用容斥原理来计算。列出式子就是：∑D[S]=(1)jTj1ways[T;ST]
D[ST]:TSjTj1其中ways[S;T]表示从ST到T单向连边的方案数。........................................陈立杰(清华大学交叉信息学院)计数问题选讲February9,201511/67做法1cont.但是注意到这里的时间复杂度非常大，只能够处理到n8的情况，在当时的比赛中也就只能获得50分了。.........................