我怎么理解集合划分容斥

注：实在想切 相互再归的鹅妈妈 和 [GDKOI 2024]异或图 的，建议先开 [POI2006] KRY-Crystals 题解看一下。

天下 OIers 苦证明久矣。通过对集合划分容斥的学习，使我加深了对容斥的目的与过程的理解。

先看最原始的集合划分容斥。

相互再归的鹅妈妈

在 0 到 R 间选 N 个互不相同的数 x1~N，使它们异或和为 0，求方案数。（R<=2^1e6-1,N<=7）

用本文第一行的方法求允许存在相同的数的答案。

考虑原始的容斥。有 \(\binom N2\) 条要求，形如某两个数不相等。枚举这些要求的子集 \(S\)，表明钦定违反这些要求，求方案数乘容斥系数 (-1)^|S|，再求和。具体地，把被违反的要求看作边，连成若干连通块，钦定连通块内部选的 x 两两相等，求方案数。注意这里不要求一个连通块选的 x 不与其他连通块选的 x 不相等，我称之为连通块方案。

交换求和顺序算贡献。发现对于一个考虑到的连通块方案，其容斥系数和，就是满足 S 中的边连成的连通块方案恰符合此方案，(-1)^|S| 之和。

计算这个容斥系数和。对每个连通块分别考虑，最后乘起来就行。设 f(n) 表示 n 个点，边集 S 满足图连通，\(\sum(-1)^{|S|}\)。设 g(n) 表示 n 个点，任何一个边集 S，\(\sum(-1)^{|S|}\)。注意到 g(n)=[n=1]。这里用个小容斥，枚举 1 所在连通块大小 i，可得 \(f(n)=g(n)-\sum_{i=1}^{n-1}\binom{n-1}{i-1}\cdot f(i)\cdot g(n-i)=[n=1]-f(n-1)(n-1)\)，边界 f(1)=1，归纳可得 f(n)=(-1)^n-1(n-1)!。

这样，就可以枚举连通块方案（即集合划分方案，总数为 Bell 数），设奇数大小连通块个数为 m，求任选 m 个数异或和为 0 的方案数，乘上容斥系数，求和，就是答案。

以上是个硬核方法。以下来个有目的性的方法。

对于一个真实的连通块方案（即严格满足 x 相同的在同一连通块，不同的在不同的连通块），记 ai 表示第 i 个连通块大小，计入的次数为 [x 互不相同]=\(\prod [a_i=1]\)