有一些没有见过的推论：

$\color{blue} f(n)=\sum\limits_{i=0}^n (-1)^i {n\choose i}g(i)\Leftrightarrow g(n)=\sum\limits_{i=0}^n (-1)^i{n\choose i}f(i)$

$\color{orange}f(n)=\sum\limits_{i=0}^n{n\choose i}g(i)\Leftrightarrow g(n)=\sum\limits_{i=0}^n(-1)^{n-i}{n\choose i}f(i)$

$\color{blue}f(n)=\sum\limits_{i=n}^{m}(-1)^i{i\choose n}g(i)\Leftrightarrow g(n)=\sum\limits_{i=n}^{m}(-1)^i{i\choose n}f(i)$

$\color{orange}f(n)=\sum\limits_{i=n}^m{i\choose n}g(i)\Leftrightarrow g(n)=\sum\limits_{i=n}^m(-1)^{n-i}{i\choose n}f(i)$

需要注意后面的两种情况的组合数与 $m$ 无关，最常见的还是第四种形式。

对于二维的情况也是类似的，这里只举第 $4$ 个作为例子：

$f(n,m)=\sum\limits_{i=n}^p\sum\limits_{j=m}^q{i\choose n}{j\choose m}g(i,j)\Leftrightarrow g(n,m)=\sum\limits_{i=n}^p\sum\limits_{j=m}^q(-1)^{n+m-i-j}{i\choose n}{j\choose m}f(i,j)$

BZOJ2839 集合计数

设 $f(k)$ 表示钦定 $k$ 个元素是集合的交集的方案，那么有：

$f(k)={n\choose k}\times (2^{2^{n-k}}-1)$

设 $g(k)$ 表示恰好选了 $k$ 个元素的方案数，可以得到：

$f(k)=\sum\limits_{i=k}^n{i\choose k}\times g(i)$

反演可以得到：

$g(k)=\sum\limits_{i=k}^n(-1)^{i-k}{i\choose k}f(i)=\sum\limits_{i=k}^n(-1)^{i-k}{i\choose k}{n\choose i}(2^{2^{n-i}}-1)$

BZOJ4665 小 w 的喜糖

考虑对答案进行容斥，设 $f_i$ 为钦定 $i$ 个不合法的情况的方案数，那么显然答案为：

$\sum\limits_{i=0}^n(-1)^i f_i$

设 $g_{i,j}$ 表示考虑前 $i$ 中颜色，其中有 $j$ 个不合法的方案数，那么有：

$g_{i,j}=\sum\limits_{k=0}^{\min(j,c_i)}g_{i-1,j-k}\times {c_i\choose k}\times{s_i-j\choose c_i-k}$

其中：

$c_i=\sum\limits_{j=1}^n [A_j=i],s_i=s_{i-1}+c_i$

时间复杂度为 $O(n^2)$。

P4859 已经没有什么好害怕的了

考虑令 $k\gets \dfrac{n+k}{2}$，这样 $a>b$ 的个数就是 $k$ 了，然后将 $a,b$ 两个数组按照升序排列。

设 $f_{i,j}$ 表示考虑 $a$ 中前 $i$ 个元素，有 $j$ 对 $a>b$ 的方案数，那么有转移方程：

$f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times(l_i-j+1)$

其中 $l_i$ 表示比 $a_i$ 小的元素中最大的下标。

设 $g(x)=f_{n,x}\times(n-x)!$ 表示钦定 $x$ 个剩下的随便选的方案数，设 $f(x)$ 表示刚好有 $x$ 被选择。

那么有关系：

$g(x)=\sum\limits_{i=x}^n {i\choose x}\times f(i)$

反演得到：

$f(k)=\sum\limits_{i-k}^n(-1)^{k-i}{i\choose k}\times g(i)$