仙人掌计数

安徽师范大学附属中学汪乐平JOHNKRAM仙人掌计数自我介绍•太弱了就不自我介绍了……•反正知道是个蒟蒻就行•贴张图说明一下•不对，贴成仙人掌的爸爸了•（还不鼓掌致敬！）仙人掌是什么•嗯，这回贴对了•如果一个无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。仙人掌是什么为什么讲这个•因为我太弱了，不会仙人掌更高端的应用啊•而且这个没有人讲过啊233333说明•本PPT中所有的图均为有标号图，且无重边和自环•图G1={V1,E1}和图G2={V2,E2}是相同的当且仅当V1=V2且E1=E2题目•给一个n(n≤30000)，对于每一个1≤i≤n，求i个点的仙人掌的个数•答案mod998244353(7*17*223+1)•大家先大胆猜一波时间复杂度分析设ai=i个点的仙人掌的个数，ci=i个点的有根仙人掌的个数（即从i个点中选一个点作为根）显然ci=i*ai令，即C(x)是ci的指数生成函数我们脑补一下删掉根结点连出去的边之后整个仙人掌变成了什么样子对每一条边分开讨论（后面的图片中，我们假设2号结点为根）1!*)C(iixciix1.边不在环上显然，删掉这条边之后，多出来的与根不连通的连通块是一棵仙人掌。把原来与根相连的点作为根结点，那么这就是一棵有根仙人掌对应的指数生成函数就是C(x)2.边在环上显然，两条边都删掉才会出现与根不连通的连通块，所以放在一起考虑设环上去掉根结点后有i个点（i≥2）显然，每个点对应了一棵仙人掌。把环上的点作为根结点，那么这个环在删掉那两条边之后就变成了i棵有根仙人掌组成的链因为链可以翻转，所以对应的指数生成函数是2)(Cix综合边在不在环上以及在环上时i的值都是可以任意的所以删掉根连出去的边之后，一个与根不连通的连通块对应的指数生成函数就是连通块的个数也是任意的，而且连通块之间是无序的，所以所有连通块组成的集合对应的指数生成函数就是把根节点加回去，就又变回了一棵仙人掌，而指数生成函数要乘上x，所以仙人掌对应的指数生成函数就是显然，这个式子是等于C(x)的，所以我们可以列出方程：用多项式牛顿迭代解这个方程即可得到C(x)，然后计算ci和ai即可接下来分析一下时间复杂度)(22)()(2)(22)()(2)()(222xCxCxCxCxCxCxCxCii)(222)()(2xCxCxCe)(222)()(2xCxCxCex)(222)()(2)(xCxCxCexxC时间复杂度考虑需要进行哪些运算多项式加法多项式减法多项式求导多项式乘法多项式求逆多项式Exp前三项运算是O(n)的，后三项操作是O(nlogn)的所以迭代一次的时间复杂度是O(nlogn)所以总的时间复杂度T(n)=T(n/2)+O(nlogn)=O(nlogn)嗯，没错，就是O(nlogn)，n=30000的O(nlogn)由此可见常数有多大但是，不管怎么样，我们完美地解决了这个问题！应用可以看出，考虑每个环对答案的贡献这种思想是很有用的于是很多计数题、期望题都能做了，如：沙漠计数（每个连通块都是仙人掌的无向图）仙人掌生成树个数期望仙人掌生成森林个数期望沙漠生成森林个数期望……靠！怎么全是仙人掌！有没有不是仙人掌的东西！有啊下一页来讲一道不是仙人掌的题目点双连通图计数•给一个n(n≤30000)，求n个点的点双连通图个数•答案mod998244353(7*17*223+1)•大家先大胆猜一波时间复杂度分析WTF？这跟仙人掌有什么关系？嗯，我们考虑对一个连通图求点双连通分量有一个众所周知的性质：任意一条边属于且仅属于一个点双连通分量（两个点一条边也属于点双连通图）是不是很像仙人掌了？点双连通分量就相当于环，只不过把不在环中的边变成了两个点的环！设bi=i个点的点双连通图个数，di=i个点的有根无向连通图个数（找不到更恰当的词了……），B(x)和D(x)分别表示bi和di的指数生成函数类似的列出方程考虑怎么解这个方程))(('!)(11)(xDBixDbexexxDiii解方程先移项设D-1(x)满足D(D-1(x))=x，将原式中的x全部替换为D-1(x)：使用多项式Ln即可在O(nlogn)的时间内求出D(x)如果要准确计算B(x)，最好时间复杂度O((nlogn)1.5)但本题只需要求出第n项，可以使用拉格朗日反演做到时间复杂度O(nlogn)xxDxDB)(ln))((')(ln)('1xDxxB计算过程拉格朗日反演（[xn]F(x)表示F(x)中xn项的系数）：本题中，将x替换成D(x)可得使用多项式Ln即可在O(nlogn)的时间内计算出G(x)至于求多项式的n次方，如果用快速幂计算时间复杂度是O(nlog2n)的显然，使用多项式Ln和多项式Exp可以将时间复杂度降至O(nlogn)所以总的时间复杂度就是O(nlogn)问题得到了完美的解决！nnnnxFxxGxxFGx))()(('][))((][111)(ln))((11xDxxDGxxDxG)(ln)()(ln)(ln)()(xFkxGxFxGk参考资料彭雨翔《IntroductiontoPolynomials》金策《生成函数的运算与组合计数问题》感谢感谢CCF提供这次交流的机会感谢罗哲正提供了这个Idea感谢彭雨翔、金策等前辈对生成函数和多项式算法的研究感谢大家的聆听THEEND