【OI之路】03数学-16快乐计数

快乐计数

努力更上时代潮流ing

前置:多项式全家桶、生成函数(包括拉格朗日反演)

以下计数的所有图都没有重边

带标号无向图

以下所有生成函数都是EGF

Prufer序列

背结论:带标号无根树和Prufer序列是双射,详情:matrix67

树转序列:每次找到编号最小的叶子节点,输出x的相邻节点,删除x,共n-2次

Cayley公式:n个节点完全图的生成树个数=$n^{n-2}$;

推论:设编号为i的节点度数为$d_i$,显然每个数会出现$d_i-1$次,直接多重集排列数,树的个数=$\frac{(n-2)!}{\prod (d_i-1)!}$

树个数的另一种推导

我更喜欢这种,而且对下面有启发意义

考虑有根树的EGF,$F(x)=xe^{F(x)},F^{-1}(x)=\frac{x}{e^x},拉格朗日反演,[x^n]F(x)=\frac{1}{n}[x^{n-1}] (F^{-1}(x)/x)^{-n}=\frac{n^{n-1}}{n!}$

基本结构计数

$$
Tree(x)=\sum_{i=0} i^{i-2} \frac{x^i}{i!},Trees(x)=ln\ Tree(x) \\UndirectedGraph(x)=\sum_{i=0} 2^{C_i^2} \frac{x^i}{i!},UndirectedConnectedGraph(x)=ln\ UndirectedGraph(x)
$$

例题:Hdu5279 YJC plays Minecraftcode
$$
对于一个块,森林生成树如上,不考虑环的话就是 2^{n} \prod ts(a_i) \\
简单容斥掉,首先跨块的边要连上,设g(n)表示大小为n的去头去尾块方案数\\
g(n)=\sum_{i=2}^n C_{n-2}^{i-2} i^{i-2} ts(n-i),直接卷即可
$$

51nod1728 不动点,考虑有根树EGF转森林,$ans(k)=e^{x*ans(k-1)}$

仙人掌

首先仙人掌是一个很有特征的结构,就是环与环只能用点连接
$$
设有根仙人掌的EGF为C(x),考虑去掉根后剩下什么,对于每个联通块分析 \\
如果原本用非环边相连,则EGF为C(x),否则设环大小为t,考虑到环可以翻转,EGF=\sum_{i=2}^{\infty} C^t(x)/2 \\
常规操作地把各个联通块exp起来,C(x)
=x*exp(C(x)+\sum_{i=2}^{\infty} C^t(x)/2)
=x*exp(\frac{2C(x)-C^2(x)}{2-2C(x)}) \\
直接牛迭,g(b)=\frac{2b-b^2}{2-2b}满足exp条件,链式法则得B=b-\frac{b-xe^{g(b)}}{1-xe^{g(b)}g’(b)} \\
使用商法则g’(b)=\frac{(2-2b)^2+2(2b-b^2)}{(2-2b)^2}=\frac{1}{2}+\frac{1}{2b^2-4b+2}
,巨常数O(nlogn)
$$
注意到我们考虑有根来便于拼接,而且能方便地从这个特殊点入手,考虑剩下的各个联通块的情况

例题:Loj6569 仙人掌计数 ,你会发现我的板子在应对这种复杂函数的时候非常好写,rose牛迭30行我6行,还跑得更快,code

点双联通图计数

考虑怎样化一个跟点双有关的式子出来,设$s_i$表示大小为i的点双图的个数($s_1=0$,EGF为S);

一开始可能想着去掉点双的根,但这样似乎不太行;考虑用点双表示连通图,设带标号有根无向联通图个数的EGF为F

我们从连通图的根入手,根可能在多个点双内,但如果将根去掉形成若干联通块,则每个联通块恰有一个点双包含根节点,那每个联通块其实就是由中间的点双+挂在点双上点的小联通块组成的
$$
枚举点双大小,大小n联通块的贡献=[x^n]\sum_{i=1}^{\infty} s_{i+1} \frac{F^{i}(x)}{i!}=[x^n] S’(F(x)) \\
那么考虑多个联通块拼接,F(x)=xe^{S’(F(x))},可得F^{-1}(x)=\frac{x}{e^{S’(x)}} \\
不能牛迭,而拉格朗日反演每次只能求一个系数,所以我们需要进一步化式子来快速求出S’ \\
设T(F^{-1}(x))=S’(x)=ln \frac{x}{F^{-1}(x)},T(x)=ln \frac{F(x)}{x}可计算,于是我们顺利地用复合逆表示出S’ \\
直接拓展拉格朗日反演,{[x^t]} S’(x)={[x^t]} T( F^{-1}(x) )=\frac{1}{t} [x^{t-1}] T’(x) \frac{1}{(F(x)/x)^t} \\
$$
例题:loj6363 地底蔷薇 code
$$
设A’为S’只保留题目要求的位置,先求出A’,由上复杂度为O((\Sigma t)log(\Sigma t)) \\
所求为B(x)=xe^{A’(B(x))},B^{-1}(x)=\frac{x}{e^{A’(x)}} \\
用普通反演搞回去就可以得到B了,ln(B^{-1}(x)/x)=-A’(x),此处为O(nlogn) \\
细节:F/x满足ln条件,直接-t次方算,A’满足exp条件
$$

边双联通图计数

和上面类似的思路,但你注意到考虑删点并没有什么用……不妨考虑根所在的边双

设有根边双图的EGF为B,带标号有根无向联通图个数的EGF为F,$B(x)=\sum_{i>0} \frac{b_ix^i}{i!} e^{iF(x)}$ 表示可以任选若干位置挂上一个连通图
$$
F(x)=\sum_{i>0} \frac{b_ix^i (e^{F(x))^i}}{i!}=B(xe^{F(x)}),不能牛迭同样考虑复合逆 \\
设T(x)=xe^{F(x)},F(x)=B(T(x)),B(x)=F(T^{-1}(x)),符合拓展拉格朗日反演的式子 \\
{[x^n]}B(x)={[x^n]}F(T^{-1}(x))=\frac{1}{n} [x^{n-1}]F’(x)(T(x)/x)^{-n},O(nlogn)
$$

带标号有向图

参考:国家集训队2017论文集的《A + B Problem》命题报告

为下文方便定几个符号

有向生成函数DGF(瞎起的名字,出现在Johnkram的ppt里):$S(x)=\sum_{i \ge0} a_i \frac{x^i}{i!2^{C_{i}^2}}$

意义:$(A(x)*B(x))[x^n]=\sum_{i=0}^n C_n^i2^{i(n-i)} a_ib_{n-i}$ 即定向连边

g为DAG数,其EGF为G,DGF为GG;h为有向图数,其EGF为H,其DGF为HH;d为强连通图,其EGF为D,其DGF为DD

竞赛图相关计数

核心思想:把握竞赛图的特性,缩点后一定是链,任意两个两个强连通分量间都满边且同向

强连通竞赛图计数

这东西大概是有向图里面最简单的吧,不用DGF

设G为所有竞赛图,F为强连通竞赛图,为方便设$g_o=1,f_0=0$

考虑怎么表示,一开始想着考虑1在哪里发现不好搞,但想了想发现改为枚举哪些点作为拓扑序上第一个就好了(缩完点显然是链),$g_n=[n=0]+\sum_{i=1}^{\infty}C_n^if_ig_{n-i},G=1+F*G$

例题:luogu4233 射命丸文的笔记code

哈密顿回路数=$(n-1)!2^{n(n-1)/2-n}$,然后有哈密顿回路的竞赛图等价于强连通的竞赛图,证明

要特判一下1和2,$O(nlogn)$

bzoj5219 Lydsy2017省队十连测 最长路径code

先把上面的f和g处理好,考虑s表示以1所在强连通分量为开头的方案数,$s_n=\sum_{i=1}^nC_{n-1}^{i-1}f_ig_{n-i},ans_i=C_{n-1}^{i-1}s_ig_{n-i}$

竞赛图强连通分量个数 GDOI2018 D1T4

有向无环图计数

例题
$$
同样考虑有根,定义根为出度=0的节点,考虑简单容斥 \\
至少i个节点是根,考虑根与其他节点的连边,g_n=[n=0]+\sum_{i=1}^n(-1)^{i+1} C_n^i2^{i(n-i)}g_{n-i}
$$
论文上的是一个稍复杂的思路,选看:

请先思考后再展开

$$
显然无根dag(G,根集合S)对应2^{|S|}个有根dag(G,S’),设i个点j个根的无根dag为f_{i,j},考虑将j个点删除会发生什么 \\
考虑选哪些点为根以及删除的边,\sum_{实际i=0}^n f_{n,i} 2^i=\sum_{至少i=0}^n C_n^i 2^{i(n-i)} g_{n-i}\\
展开次幂并翻转,\sum_{至少j=0}^n \sum_{i=j}^n f_{n,i} C_i^j=\sum_{至少i=0}^n C_n^i 2^{i(n-i)} g_{n-i} ,注意外和号等价 \\
\sum_{i=0}^n (-1)^i C_n^i 2^{i(n-i)} g_{n-i}
=\sum_{j=0}^n (-1)^j \sum_{i=j}^n f_{n,i} C_i^j
=\sum_{i=0}^n f_{n,i} \sum_{j=0}^i C_i^j (-1)^j=\sum_{i=0}^n f_{n,i} [i=0]=[n=0]\\
整理可得递推式:g_n=[n=0]-\sum_{i=1}^n (-1)^i C_n^i 2^{i(n-i)} g_{n-i}
$$
殊途同归,也算是某种验证吧

根据生成函数知识可得:$PP为(-1)^i的DGF,GG=-PP*GG+GG+1,GG=PP^{-1}$

若要求弱连通,直接在EGF下ln就好了

题:CEOI2019游乐园人类补完计划

强连通图计数

例题

考虑怎么类似于上面去做,就是要把一些强连通分量替代前面枚举的根,从上面的式子出发,就是要用$(-1)^i$作为至少i个强连通块作为根组合起来的系数,故设$e_n$表示总点数为n的,若干个强连通图,且方案的系数为$(-1)^{强连通分量个数}$
$$
枚举1所在强连通分量大小,e_n=[n=0]-\sum_{i=1}^n C_{n-1}^{i-1} d_i e_{n-i},E=1-\int D’E,D=-\int \frac{E’}{E}=-lnE \\
类似dag的推导,还是容斥,\sum_{i=0}^n C_n^i e_i 2^{i(n-i)}h_{n-i}=[n=0],即EE=HH^{-1} \\
可以理解为对h_n减一系列东西,这些东西的和是个容斥,意义为所有强连通分量根的个数>0的情况,于是=0
$$

顺便说一道类似的题:bzoj3812 主旋律,$O(n3^n)$,code
$$
e_S=[S=\emptyset]-\sum_{T \subseteq S,lowbit(S) \in T} d_T e_{S \setminus T} 得d_S=[S=\emptyset]-e_S-\sum_{T \subset S,lowbit(S) \in T} d_T e_{S \setminus T} \\
把上面的式子化一化,e_S=[S=\emptyset]-\sum_{T \subset S} 2^{to(T,S \setminus T)} e_T h_{S \setminus T} \\
$$

国家集训队互测2016R1 A+B problem(口胡)

若为dag,考虑对每个点考虑自己贡献,而每个点都一样,$ans=\sum_{i=1}^n i*2^{i-1}*g2_{i-1}$

那现在也是类似的,先搞出合法的强连通分量D2,进而求合法的E2,然后是H2,以及他们对应的DGF

$ans=\sum_{i=1}^n \sum_{j=1}^i C_i^j 2^{j(i-j)} *d2_jh2_{i-j}=\sum_{i=1}^n [x^i]DD2*HH2$

形式化来说,定义一元运算$\Delta$表示将后面的EGF转化为DGF,$[x^i]=(\Delta D2)*(\Delta (e^{-D2}))^{-1}$

无标号图

不会告辞

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/9763.html
转载请注明出处,谢谢!