集合划分容斥
ForgotMe
·
2025-02-27 17:21:25
·
题解
感觉是非常牛的一个 trick 啊。
啥是集合划分容斥呢？可以理解为在某种等价关系下，对于某一组合结构，构成其的元素其可以被划分成若干等价类，然后有一个关于等价类的贡献系数 F(x)，对于一种方案，需要关注其极大等价类，但是一般来讲，极大等价类很难直接得到刻画。而如果直接采用对一般情况下的等价类计数，肯定会算重。不如考虑对给等价类一个系数 H(x)，假设合并方式为 G(x)，则让：
G(H(x))=F(x)
注意这里并不是指多项式复合，可以理解为以某种方式合并等价类，即一个极大等价类可能会被若干个等价类组合而成的所有方式。
AT_arc134_f [ARC134F] Flipping Coins
集合容斥划分的经典例题。
对于一个置换环，注意到其最后正面朝上的硬币个数就是长度为奇数的极长上升连续段个数。那么得到 F(x)=\sum [2|(i-1)]wx^i。考虑对一个长度为 i 的连续段，设计一个容斥系数 h_i，记作 H(x)，那么根据连续的合并方式，即 \dfrac{1}{1-H(x)}-1=F(x)。通过简单的解方程可以把 H(x) 解出来。接下来就不需要考虑极大上升连续段这个限制了。由于是置换环，考虑断环为链，以整个环的最小值作为起点展开。那么有式子：
\sum \dfrac{H^i(x)}{i}=\ln(1-H)
除以 i 是因为从最小值开始，而一种有 i 个连续段的方式会被恰好算 i 次。于是就得到了一个环的 EGF。做一个 exp 即可。
其实集合划分容斥是非常格式化的一个东西，定义啥是一个等价类，然后推出容斥系数，正常计数即可。
https://www.luogu.com.cn/article/ov7ptv00
例题大概就是上面这个博客里写的。