NOI2015冬令营陈立杰《计数》

........................................计数问题选讲陈立杰清华大学交叉信息学院February9,2015陈立杰(清华大学交叉信息学院)计数问题选讲February9,20151/67........................................intro.￿￿￿￿￿￿￿￿￿￿￿￿陈立杰(清华大学交叉信息学院)计数问题选讲February9,20152/67........................................TableofContents1Part1.有趣的容斥原理2Part2.dp套dp3Part3.有技巧的枚举(分类)4Part4.期望的线性性陈立杰(清华大学交叉信息学院)计数问题选讲February9,20153/67........................................Part1.有趣的容斥原理大家应该都知道容斥原理吧。好了，我们已经知道这个模型是怎么回事了，让我们看几道题目来学习一下吧！陈立杰(清华大学交叉信息学院)计数问题选讲February9,20154/67........................................Biconnected给你一个n(n10)个点的无向简单图，问有多少个边的子集E′E,使得只保留E′中的边的话，整个图是双联通的。也就是问你有多少个关于边的子图（点集合还是这n个点）双连通。2014ACM/ICPCAsiaRegionalAnshanOnline,byme.陈立杰(清华大学交叉信息学院)计数问题选讲February9,20155/67........................................做法1直接处理这个问题并不容易，不妨考虑如何计算使得整个图不双联通的边集。注意到一个不双联通的图，必然能够唯一地分成几个双联通块，并且这些块之间组成了一棵森林。陈立杰(清华大学交叉信息学院)计数问题选讲February9,20156/67........................................做法1cont.那么我们不妨先枚举这个图如何被划分成了几个联通块，然后计算这些联通块之间连成森林的方法数即可。每个联通块连成双联通图的方案数就是一个子问题了，集合dp计算即可。后者是一个经典问题，我们先枚举森林中哪些点组成了树，然后使用生成树数量的计数公式即可。复杂度比较高，所以只能处理n10。陈立杰(清华大学交叉信息学院)计数问题选讲February9,20157/67........................................做法2abs.使用和下面一个题目类似的方法可以做到n15。陈立杰(清华大学交叉信息学院)计数问题选讲February9,20158/67........................................sconnect给你一个n(n15)个点的有向简单图，问有多少个边的子集E′E,使得只保留E′中的边的话，整个图还是强连通的。2014TsinghuaTrainingCamp,byme.陈立杰(清华大学交叉信息学院)计数问题选讲February9,20159/67........................................做法1还是非常难直接处理这个问题，和上一题类似，我们来考虑如何非强连通的子图数量。相信聪明的同学立马就发现了，非强联通的图当然就是一些强连通分量组成的DAG啦。那么我们立刻有了简单粗暴的做法1，枚举分成强联通分量的划分方案，对于每一个划分计算连成DAG的方案数。陈立杰(清华大学交叉信息学院)计数问题选讲February9,201510/67........................................做法1计算DAG那么我们现在需要考虑这个问题，给你n个点的图，计算有多少子图是DAG。这个问题也是一个非常经典的问题，我们可以采用集合dp，令D[S]表示S这个集合有多少子图是DAG，我们知道一个DAG就会有一些没有出度的汇点，那么我们枚举S中汇的集合T，不能保证SnT中就没有汇，可能出现重复计算。所以可以使用容斥原理来计算。列出式子就是：D[S]=∑T　SjTj1(1)jTj1ways[T;ST]
D[ST]:其中ways[S;T]表示从ST到T单向连边的方案数。陈立杰(清华大学交叉信息学院)计数问题选讲February9,201511/67........................................做法1cont.但是注意到这里的时间复杂度非常大，只能够处理到n8的情况，在当时的比赛中也就只能获得50分了。陈立杰(清华大学交叉信息学院)计数问题选讲February9,201512/67........................................做法2要优化时间复杂度，我们来仔细的观察一下这个计算。注意到，实际上我们没有必要预先枚举集合划分，我们可以直接枚举T，表示汇的强连通分量构成的集合是哪些，然后dp出T内部拆成奇数个强连通分量的方案数减去拆成偶数个强连通分量的方案数。那么实际上我们就一下子把那么多容斥一起计算了。在通过一些技巧预处理ways这个数组，那么复杂度就只有O(3n)了。陈立杰(清华大学交叉信息学院)计数问题选讲February9,201513/67........................................Biconnected做法2那么联系到biconnected这个题目，我们实际上也可以通过枚举叶子的集合，来容斥的计算生成树的个数。使用和上一题一模一样的方法，也可以在O(3n)的时间内解决这个问题了。陈立杰(清华大学交叉信息学院)计数问题选讲February9,201514/67........................................EndlessSpin有一行N个白色的球，每次你会随机选择一个区间[l;r]，将这些区间里的球都染黑。问期望多少次以后，所有的球都被染黑？2013Multi-UniversityTrainingContest3,byme.陈立杰(清华大学交叉信息学院)计数问题选讲February9,201515/67........................................做法1首先我们注意到，期望次数等于:1∑L=0P[L]:其中P[L]表示我们进行了L次操作后，还没有全部染黑的概率。这个式子是非常直观的。陈立杰(清华大学交叉信息学院)计数问题选讲February9,201516/67........................................做法1那么接下来我们考虑如何计算P[L]，注意到在进行了L次操作后还没有全部染黑，意味着存在一些球，L次操作以后还是白色的。那么我们不妨考虑使用容斥原理，枚举这些到最后也是白色的球有哪些。然后进行计算。不妨假设这些白色球分别是v1;v2;:::;vk，那么只能在区间[1;v11];[v1+1;v21];:::;[vk+1;n]的子区间中选择。如果这样的子区间一共有A个，那么每次选到他们的概率就是:p=A(n+12):陈立杰(清华大学交叉信息学院)计数问题选讲February9,201517/67........................................做法1cont.L轮都选到他们的概率就是pL。注意到既然使用了容斥原理，那么如果有奇数个白球，P[L]就加上pL，否则就减去pL。显然∑1i=0pL=11p。所以直接处理11p即可。那么考虑dp，来计算上面的值，注意到我们只需要记录上一个目前的白点数量的奇偶性，目前可以选择的区间数，然后枚举下一个白点的位置即可。陈立杰(清华大学交叉信息学院)计数问题选讲February9,201518/67........................................做法2先介绍一个容斥原理的简单变形。考虑我们有随机变量X1;X2;:::;Xn，我们想要计算E[max(X1;X2;:::;Xn)]。我们有如下的式子：E[nmaxi=1(Xi)]=∑S[n];jSj1(1)jSj1E[mini2SXi]:注意到这个式子其实是显然的，考虑Xi都是离散的简单情况。不妨直接将Xi表示成集合1;2;:::;Xi，那么max就是它们的和的大小，min就是它们的交的大小。这个式子立马就变成了原来的并，交形式的容斥原理。由期望的线性性立刻就能得到这个式子。对于Xi不是离散的情况，反正大家也用不着_，呵呵哒。陈立杰(清华大学交叉信息学院)计数问题选讲February9,201519/67........................................做法2那么我们令Xi表示第i个球在哪一轮被染黑。那么我们想要计算的其实就是E[maxni=1(Xi)]。这个并不好计算，通过之前的那个式子，我们能将问题转化成计算(1)jSj1E[mini2SXi]，进一步的分析能够得到和做法1一模一样的方法。所以说这里其实只是思路不同啦，做法最后还是一样的_。陈立杰(清华大学交叉信息学院)计数问题选讲February9,201520/67........................................TableofContents1Part1.有趣的容斥原理2Part2.dp套dp3Part3.有技巧的枚举(分类)4Part4.期望的线性性陈立杰(清华大学交叉信息学院)计数问题选讲February9,201521/67........................................Part2.dp套dp简单地说就是通过一个外层的dp来计算使得另一个dp方程(子dp)最终结果为特定值的输入数。(我坦白这名字是我瞎YY的)。那么，这个问题要怎么解决呢，我们不妨一位一位确定子dp的输入，不妨考虑已经枚举了前i位了，那么注意到，由于我们只对dp方程的最终结果感兴趣，我们并不需要记录这前i位都是什么，只需要记录对这前i位进行转移以后，dp方程关于每个状态的值就可以了（这个的意思是，外层dp的状态是所有子dp的状态的值）。陈立杰(清华大学交叉信息学院)计数问题选讲February9,201522/67........................................Part2.dp套dpcont.看一个简单的例子，假设我们有一个DPA。A读入一个序列a1;a2;:::;an.返回关于这个系列的一个结果。现在我们想要知道有多少种a的序列可以返回这种结果。陈立杰(清华大学交叉信息学院)计数问题选讲February9,201523/67........................................Part2.dp套dpcont.这种要怎么做？考虑第一个DP,A，如果我们a1;a2这么依次枚举。那么当我们处理到a1;a2;:::;ai的时候，有意义的只有A目前每个状态的值。也就是说，我们可以在状态里面记录“A的所有状态的值”。好了，我们已经知道这个模型是怎么回事了，让我们看几道题目来学习一下吧！陈立杰(清华大学交叉信息学院)计数问题选讲February9,201524/67........................................Heromeetdevil给你一个只由AGCT组成的字符串S(jSj15)，对于每个0ijSj，问有多少个只由AGCT组成的长度为m(1m1000)的字符串T，使得LCS(S;T)=i？LCS就是最长公共子序列。2014Multi-UniversityTrainingContest4,byme.陈立杰(清