《顾昱洲营员交流资料》由会员分享，可在线阅读，更多相关《顾昱洲营员交流资料（38页珍藏版）》请在金锄头文库上搜索。
1、Graphical Enumeration 南京师范大学附属中学 顾昱洲 Sevenkplus 吐槽 & 回答 Q：你是谁？我听都没听说过！ A：我是南京师范大学附属中学顾昱洲，常用 ID Sevenkplus。 Q：你这么弱，讲的东西肯定很弱吧。 A：对。本课件内容较弱，请各位神牛、教主 （特指）选择性听讲或睡觉。 Q：标题为啥是Graphical而不是Graph？ A：恩，这是个有水平的吐槽。但是你肯定没 听说过一本和标题同名的书。 Problem 求n个点的_的个数。 (某些题中不限点数，会特别说明) Warmup 有标号无向图 所有点度都是偶数的有标号无向图 有标号有根树 有标号无根树
2、 无标号二叉树 标号为k的点度为vk的无根树 无标号毛毛虫 Warmup 有标号无向图 所有点度都是偶数的有标号无向图 有标号有根树 有标号无根树 无标号二叉树 标号为k的点度为vk的无根树 无标号毛毛虫 22nC2 12nC1nn 2nn2 1n nC n+(2)! (1)!kn v 4 4222n n +经典题 有标号DAG 要求O(n2)算法 经典题 contd 考虑入度为0的点的个数 F(n, m)表示n个点，恰好m个点入度为0的有 标号DAG个数 O(n3) ()1( ,)(21) 2(, )n m mkm n m km n kF n mC F nm k =经典题 contd 考虑枚
3、举一个子集S F(n, S)为S中的顶点度为0的DAG个数 G(n, S)为仅S中的点度为0的DAG个数 F的递推式是显然的 F与G的关系 | |(| |)( , )2(|,)S nSF n SF nS=( , )( , )TSF n SG n T=经典题 contd 反演(容斥原理) 结合以上式子 设|S|=m，化简该式 | | | |( , )( 1)( , )TSTSG n SF n T=| | | | |(| |)( , )( 1)2(|,)TST n TTSG n SF nT=()( , )( 1)2(,)k mk mk n k n m m k nG n SCF nk =经典题 co
4、ntd 对|S|相同的式子求和 然后化简F (详见下一页) 有公式恐惧症者建议先休息一会儿 (为了节省页面，先写复杂度) O(n2) 1| |()1| |()1()11()11( ,)( , )( 1)2(,)( 1)2(,)2(,)( 1)2(,)( 1)m n Smk mk mk n k n m m n Sm m k nmk mk mk n k nn m m nm k nk n kk mmk m nn m k nm kk n kk mkm nk m kF nG n SCF nkCCF nkF nkC CF nkC C= = = 1()1( 1)2(,)k nkk n kk n k nC F
5、 nk+ =SPOJ KPGRAPHS 有标号连通图 有标号欧拉图 有标号二分图 要求n=11000的所有答案 模109+7 代码长度限制7000B SPOJ KPGRAPHS contd 已知n个点的满足P的图的个数S(P, n) 求连通的n个点的满足P的图的个数F(P, n) 令G(P, n) = S(P, n) - F(P, n) 时间复杂度 O(n2) 1 1 1 1( , )( , ) ( ,)n i n iG P nCF P i S P ni =SPOJ KPGRAPHS contd 连通图 P=True 欧拉图 P=所有点的度都是偶数 二分图？ SPOJ KPGRAPHS con
6、td 算两次 (Double Counting) 考虑对于每个二分图，点黑白染色，使得 同色点之间无边的方案数的和S 一方面，考虑黑色的点的数目，有 ()02n ii n i n iSC=SPOJ KPGRAPHS contd 另一方面，令F(n, k)为n个点k个连通块的二 分图的个数 若F(n, k) (k1)求出，那么F(n, 1)也求出 1( , )2n iiSF n i=又有SPOJ KPGRAPHS contd 对于k1，有 时间复杂度O(n3) TLE 如何解决？不属于这里讨论的内容 : ) 1 1 1 1( , )( ,1) (,1)n i n iF n kCF iF ni k
7、 =SGU 481 n个点n条边的有标号连通图 不取模 nn) SPOJ PT07D contd 先求有根树，设答案为an 考虑一个暴力过程，枚举根的每个大小的 子树的个数，设大小为k的子树有ck个。 考虑母函数 1231 23.10kkkc nac cccnkaC+ + = =0( )k k kA za z=SPOJ PT07D contd 根据暴力的递推式化简A(z)，得到 然后再根据这个式子进行一些推导，得到 这是个O(n2 log n)的DP。通过部分和优化可 以优化到O(n2)。 0()( )exp()kkA zA zzk=11 101nninij nijiaiaan+ = =SPO
8、J PT07D contd 无根树 设答案为bn 这里需要用到下一题中用到的技巧，因此 我们先讲下一题。 范浩强 Alkane 无根无标号每个点度不超过4的树(烷烃) 不取模 n=300 范浩强 Alkane contd 先计算1n的烷基(有根)个数 采用DP+最小表示(当然你也可以称之为容斥 原理或暴力乱搞或其他什么东西)可以很容 易地计算。 不考虑高精度，时间复杂度O(n2) 范浩强 Alkane contd 计算烷烃个数的难点：重复计算 唯一性 树的质心 (关于这里的翻译，英文中centroid是质心， 而重心是centre of gravity，因此我认为应该 翻译成质心) 以该点为根
9、，最大的子树最小 范浩强 Alkane contd 也可以说，以其为根，每个子树大小都不 超过n/2 于是可以继续使用最小表示()求。 特殊情况：双质心 n/2-1-A-B-n/2-1 容斥掉 不考虑高精度，时间复杂度O(n2) SPOJ PT07D contd 回来讲这题。 同样使用树的质心进行计算。 由于我们计算的是所有有根树，所以我们 在根非质心时删除掉那些有根树。 如果某个点X不是质心，那么必然存在一棵 子树大小超过n/2。（定义，反之亦然） 0/2nnin i inbaa a =SPOJ PT07D contd 当然，n为偶数的时候会有双质心。容斥掉 就好了。 求b在求出a之后是线性
10、的。 总时间复杂度O(n2) SPOJ PT07D contd Some Notes 如果你看不懂母函数，建议去看具体数学 (别看中文版)。 之前由于篇幅所限没法写推导过程，建议大家 自己去推一下，还是很有意思的。 如果实在推不出来，去看华东师大一附中赵爽 写的树的计数。 经典题 无标号最长链为n的二叉树 取模 要求线性算法 (这题点数无限制) 经典题 contd 点的个数可能特别多 考虑求最长链过程 Ans=max(Ans, HeightLefti+HeightRighti+1) 有用量只有Height Fi为深度为i，最长链为n的二叉树的个数； Gi为深度为i，最长链小于n的二叉树个数。 经典题 contd 深度为i的二叉树至少有一棵子树深度为i-1 可以写出DP方程（好长的，一行写不下） 维护F和G的部分和 O(n) 解决图计数问题的一般思路 oeis.org 唯一性 算两次 一定的数学基础 习题 证明n个点的无标号毛毛虫的个数为 思考为什么无标号图计数一般比有标号图 计数难做，并对于n非常小的情况给出一种 通用的解法 (不要枚举所有图) 阅读有标号平面图计数的论文，体会其精 妙之处。 (“这东西也能做？！”) 4 4222n n +Thanks For Listening Questions are welcome.
