容斥

容斥不僅有著各式各樣的式子，還有正難則反，容斥的思想等重要的方法手段，是計數(shù)中非常核心的技術(shù)。

樸素容斥

樸素容斥就是最基本的在小學就學過的集合的容斥。

容斥原理

設每個元素有 \(n\) 個可能的屬性 \(p_i\) 表示其屬于第 \(i\) 個集合 \(S_i\)，那么對于所有集合的并集，我們有

也就是說我們賦予集合一個順序之后，如果我們知道所有 \(1\) 個、\(2\) 個、\(\cdots\)、\(n\) 個元素的集合的交集大小，我們就可以求出這 \(n\) 個集合的并集大小。這就是樸素的容斥原理的式子。

注意這里的 \((-1)^{x-1}\) 也被稱為容斥系數(shù)，也就是在容斥中讓你要求的東西的系數(shù)為 \(1\) 或者一個常數(shù)的一個函數(shù)。下面我們將證明 \((-1)^{x-1}\) 是讓每個元素統(tǒng)計貢獻為 \(1\) 的容斥系數(shù)。

證明

我們考慮某個元素出現(xiàn)在 \(m\) 個集合 \(T_1,T2,\cdots,T_m\) 中，則這個元素被統(tǒng)計的次數(shù) \(cnt\) 我們就可以用上式算出。
具體地，在每次拿 \(x\) 個集合來求并集時，由于集合被賦予了順序，所以統(tǒng)計到的貢獻就為 \((-1)^{x-1}{m\choose x}\)，即選到的 \(x\) 個集合都在這 \(m\) 個中。所以我們有

湊二項式定理可以化簡，得到

每個元素都只統(tǒng)計了一次，所以最后的總貢獻就是并集的元素個數(shù)。

應用

Luogu P3214 卡農(nóng)

在集合 \(S=\{1,2,\cdots,n\}\) 中選擇 \(m\) 個無序互異非空子集，使得每個元素被選擇的次數(shù)都為偶數(shù)，求方案數(shù)。

直接考慮無序有些困難，我們先考慮有序且符合其它限制的方案數(shù)。
注意到奇偶性的限制非常弱，實際上只用拿一個子集出來，根據(jù)其他元素被選擇次數(shù)的奇偶性來調(diào)整這個子集里的元素。這個子集是唯一確定的。其它非空互異的子集在 \(2^n-1\) 個非空子集中選擇，有

設 \(f_i\) 表示選擇 \(i\) 個互異非空子集且每個元素被選擇的次數(shù)都為偶數(shù)的方案數(shù)，答案即 \(f_m\)。容易得到 \(f_1=f_2=0\)，接下來我們考慮 DP 出 \(f_i\)。

在上式的基礎上，我們要考慮用以調(diào)整奇偶性的子集是否合法：如果前 \(i-1\) 個子集每個元素出現(xiàn)次數(shù)已經(jīng)是偶數(shù)，這個子集為空不合法，那么就要減去這不合法的方案數(shù) \(f_{i-1}\)；如果這個子集與之前某個子集相同，那除開這 \(2\) 個集合，剩下 \(i-2\) 個子集構(gòu)成了合法方案數(shù)即 \(f_{i-2}\)，先前的子集都有可能與其相同，就有 \(i-1\) 種情況，但是這兩個子集與其他子集都不相同，可能的集合就有 \(2^n-1-(i-2)\) 種。這兩部分非法方案都減去就得到了合法的 \(f_i\)，有

遞推求出 \(f_m\)，求個逆元除以 \(m!\) 轉(zhuǎn)成無序的即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e6 + 10, mo = 1e8 + 7;
int n, m, f[maxn];
ll fall_fac[maxn];

ll qpow(ll x, ll y) {
	ll res = 1;
	while(y) {
		if(y & 1) (res *= x) %= mo;
		(x *= x) %= mo, y >>= 1;
	}return res; 
}

int main() {
	ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> m; ll pow2 = qpow(2, n), fac = 1; f[0] = 1, fall_fac[1] = pow2 - 1;
	
	for(int i = 2; i <= m; i++) fall_fac[i] = fall_fac[i - 1] * (pow2 - i) % mo;
	for(int i = 2; i <= m; i++) { 
		f[i] = (fall_fac[i - 1] - f[i - 1] - (i - 1) * (pow2 - 1 - (i - 2)) % mo * f[i - 2] % mo) % mo; (f[i] += mo) %= mo;
	}
	for(int i = 2; i <= m; i++) (fac *= i) %= mo;
	
	cout << 1ll * f[m] * qpow(fac, mo - 2) % mo << endl;
	return 0;
}