分类： 母函数

题目链接

这个题一开始想歪了一直在想polya。。。带了半天队友节奏最后俩人都没整出来。

其实一开始就不该被给出的示意图带着走的，当时已经想到了剩下的是n-m段，但是关键在于没有想到怎么处理排列的去重。。。试了下用母函数分配出入度后来发现无法去除已经有圈的情况于是放弃。。其实这时候该想想能不能换个方向用母函数，哎，总的来说还是太菜，做组合数学还是不行。

后来想了下，可以先完全去掉所有的标号，也就是说把所有的点当成同一种点，然后去解决把这n个点分为n-m条链的分法，最后把标号还原回去只需要乘以一个n!的全排列系数就好了。

这时候问题转化为n个相同的点，分为n-m个链条（单个节点自身也是一个链条）的分法，而且这种分法要考虑到空间对称（参考样例）。我们可以设普通型母函数\[F(x)=a_0+a_1x+a_2x^2+…+a_nx^n\]来表示一条链的情况，幂次等于这条链条有多少个节点。由于不认为0个节点是一个链，所以\[a_0=0\], 然后当节点数多于1的时候由于空间对称要除以2，所以除了\[a_1\]之外所有的a都是1/2，也就是说对于一条链其母函数就是\[F(x)=x+1/2 x^2+1/2 x^3+1/2 x^4+….+1/2 x^n\]

得到了一条链的F(x)，由母函数的性质可以得到k条链\[(k=m-n)\]的情况就是\[F(x)^k\]的结果中\[x^n\]的系数，只不过还要乘以一个\[n!\]的系数（因为我们之前把所有球都当作一样了所以要乘以一个全排列）再除以一个\[(n-m)!\]（因为每次算出来的是所有可能的组合情况，但是这k条链条是不用排序的）

现在的话就是如何计算\[F(x)^k\]的结果中\[x^n\]的系数了，直接暴力肯定超时，考虑把\[F(x)\]的函数变换成更简单的形式。由级数的知识可以知道|x|<1时，\[ F(x)=（x-1/2 x^2)/1-x\] , 那么\[F(x)^k=x^k(1-1/2 x)^k/(1-x)^k \],\[x^k\]好处理，这说明只需要求剩下的部分的\[x^(n-k)\]的系数就行了。看剩下的部分，这里的分母看上去很难操作，但是可以再用级数的方式变换一下 \[1/(1-x)=(1+x+x^2+x^3+x^4+…+x^n)\], 也就是说要求的部分变成了 \[(1-1/2 k)^k (1+x+x^2+x^3+x^4+…+x^n)^k\], 后面的这一坨\[1+x+x^2+x^3+x^4+…+x^n\]可以认为是一次一次乘到前面的。前面的\[(1-1/2 x)^k\]可以用二项式展开，每一项为\[C_k^{i} (-1/2 )^ix^i\] 。这时候考虑计算“二项式展开中第i项对于最终结果的第j项的贡献度(i<=j)”，可以想象一下i变成j是因为加了j-i个1次幂，而总共后面乘的是k个多项式，那么所有的情况也就是中学常学的“把j-i个物品分成k份允许有空集的分法”组合问题了，答案是\[C(j-i+k-1,k-1)\]，当时高中数学老师管这叫插隔板法还是什么来着emmmmm。这时候就容易计算了，在算贡献的时候再带上（-1/2）的i次幂就行了。。。

确实是不好想，尤其是在现场赛的环境下，感觉自己还是得更多的做难一点的题目。

继续阅读“[数学][组合数学][母函数][比赛补题][×] ZOJ 4069(2018 青岛现场赛 L) Sub-cycle Graph”