详细揭秘：详细揭秘：集合划分容斥的容斥系数
宝宝都会的集合划分容斥，从多项式角度推导容斥系数
参考文献：
详细揭秘：集合划分容斥的容斥系数
2024.12.23 闲话
浅谈集合划分容斥
容斥系数简单来说就是当我们产生贡献的集合里面有 极大 等限制词语时用来拆掉这个限制所人为构造的一组系数
我们现在有两种算法
- 保证所有贡献集合都满足 极大
- 丢掉 极大 的限制
我们希望在 2 的做法中加入容斥系数使得答案和 1 算出来一样
设当前等价类合并（不限制极大的元素合并成极大的元素）的函数为 \(G\)，而在 1 中的极大集合的贡献系数是 \(F\)
那么我们构造的函数 \(H\) 满足 \(G(H(x))=F(x)\) 答案就正确了
原因就是你把所有的 \(H\) 拼起来等于它应该的系数，和正常容斥一个道理
例题
00-avoiding 序列
首先划分等价类，找到我们要容斥的东西，肯定是要对 \(0\) 的长度进行容斥
那么有 \(F(x)=x,G(x)=\dfrac{1}{1-x}-1\)
可以发现最终 \(H(x)=\dfrac{x}{1+x}\)
那么就可以直接做了，答案的生成函数是 \(\dfrac{1}{1-H(x)-mx}\)
计树
首先划分等价类，肯定划分一段连续的链是等价类
考虑如何计算，发现 \(k\) 段生成树的方案是 \(\prod\limits_i c_i n^{k-2}\)
显然合并是 \(G(x)=\dfrac{1}{1-x}-1\)，\(F(x)=\dfrac{x^2}{1-x}\)
于是 \(H(x)\) 可以简单求出，答案的生成函数就是 \(\dfrac{1}{1-\sum\limits_i ni [x^i]H(x)}\)
这里加系数是没有问题的，因为合并的时候限制了连接方式，每个合并的依然只会被多算一次
Yet Another ABC String
这个题很经典了，考虑划分等价类是 \(\text{ABCAB}\) 这样的段，因为段长最大是 \(2\)，因此生成函数是
\(F(x)=x+x^2,G(x)=\dfrac{1}{1-x}-1\) 容易知道容斥系数 \(H(x)=1-\dfrac{1}{1+x+x^2}\)
那么我们带上容斥系数连续段的生成函数是 \(\dfrac{x+y+z-3xyz}{1-xyz}\)
答案是 \([x^ay^bz^c]\dfrac{1-xyz}{1-x-y-z+2xyz}\)，手动提取系数即可