二项式反演
其实就是两个式子：
和更一般的式子（这个是至多和恰好的关系？：
和一样一般的式子（这个是至少和恰好：
证明的话暴力把一个代入另一个就行了。
至少和恰好的例子就是错排
至多和恰好的例子就是 球染色问题：
有 (n) 个球排成一行，你有 (k) 种颜色，要求给每一个球染色，相邻两个球颜色不可以相同，并且每种颜色至少使用一次
这是经常在高中数学组合那个部分见到的一个问题，只不过高中题目中数都很小
还是和刚刚的想法一样，如果没有每种颜色至少一次这个条件，那么问题很简单，答案是 (k(k−1)^{n−1})。这些方案是由恰好使用了 (i(i=0,1,2,⋯,k)) 种颜色的方案组成的，那么设 (f_i)为恰好使用了 (i) 种颜色的方案数，可以得到
[k(k-1)^{n-1} = sum_{i=0}^k {k choose i} f_i ]反演得到
[f_k = sum_{i=2}^k (-1)^{k+i} {k choose i} i(i-1)^{n-1} ]
（转自miskcoo
例题
[Luogu4859] 已经没有什么好害怕的了
Description
给定两个长度为 (n) 的序列 (a,b)。要求两两配对，使得 (a>b) 比 (a<b) 的组数恰好多 (k) 组。问方案数。(nleq 10^5)。
Sol
二项式反演套路：这个恰好不好求啊 → 诶这个至多/至少是不是可求啊 → AC
这里就是，观察到恰好不好求，但是如果是至少的话可以求啊
设 (dp[i][j]) 表示 (a) 序列的前 (i) 个，配了 (j) 对 (a>b) 的方案数。
显然有 (dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*(mx[i]-j+1)) 。(mx[i]) 表示 (b) 中小于 (a[i]) 的最靠右端点。
那么 (dp[i][j] imes (n-j)!) 就是至少配了 (j) 对的方案数，因为剩下的随便选，还是有可能再配上对。
然后套那个容斥的式子就吼了。
[BZOJ2839] 集合计数
Description
给定 (n) 个元素，相对应的就有 (2^n) 个集合。现在要在这 (2^n) 个集合中取出若干集合，使得他们的交集的元素个数为 (K)，求取法的方案数。对 (10^9+7) 取模。(nleq 10^6)。
Sol
还是那个套路。
这里发现，还是至少比较好求。
所以设 (g[i]) 表示选出来的集合交集大小至少为 (i) 的方案数。
容易发现 (large g[i]={nchoose i}cdot (2^{2^{n-i}}-1)) 。这个式子的含义是，先选出大小为 (i) 的交集具体是哪些元素，有 (large {nchoose i}) 种选法，然后包含这 (i) 个元素的集合一共有 (large 2^{n-i}) 个，每个集合都可以选或不选，但是不能选空集，所以总方案数就是 $large {nchoose i}cdot (2^{2^{n-i}}-1) $。 （但是我发现不加 (-1) 也完全( ext{ojbk})？