重修 二项式反演
开头
我只知道容斥不知道二项式反演。
反演，顾名思义就是有两个函数 \(f,g\)，知道 \(f\) 用 \(g\) 表示后反过来 \(g\) 用 \(f\) 表示。
二项式，\((a+b)^n\)，别学了二项式反演忘了二项式定理：
\[\sum_{i=0}^n\binom{n}{i}a^ib^{n-i}=(a+b)^n \]常见形式
容斥原理（无敌对称的柿子）
\[f(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}g(i) \iff g(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}f(i) \]证明
\[\begin{aligned} g(n)&=\sum_{j=0}^{n}g(j)\binom{n}{j}[n-j=0] \\&=\sum_{j=0}^{n}g(j)\binom{n}{j}\sum_{i=0}^{n-j}(-1)^i\binom{n-j}{i} \\&=\sum_{j=0}^{n}g(j)\binom{n}{j}\sum_{i=j}^{n}(-1)^{i-j}\binom{n-j}{i-j} \\&=\sum_{j=0}^{n}\sum_{i=j}^{n}g(j)\binom{n}{j}(-1)^{i-j}\binom{n-j}{i-j} \\&=\sum_{i=0}^{n}\sum_{j=0}^{i}(-1)^{i-j}\binom{n}{j}\binom{n-j}{i-j}g(j) \\&=\sum_{i=0}^{n}\sum_{j=0}^{i}(-1)^{i+j}\binom{n}{i}\binom{i}{j}g(j) \\&=\sum_{i=0}^{n}(-1)^i\binom{n}{i}\sum_{j=0}^{i}(-1)^j\binom{i}{j}g(j) \\&=\sum_{i=0}^{n}(-1)^i\binom{n}{i}f(i) \end{aligned}\]\(f\) 反过来也做一遍即得证。
容斥原理（较前者更常用）
\[f(n)=\sum_{i=0}^n\binom{n}{i}g(i) \iff g(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i) \]（呦呦呦这不是容斥嘛）
证明
设 \(h(i)=(-1)^ig(i)\)。
\[\begin{aligned} f(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}h(i) &\iff h(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}f(i) \\ f(n)=\sum_{i=0}^n\binom{n}{i}g(i) &\iff (-1)^ng(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}f(i) \\ f(n)=\sum_{i=0}^n\binom{n}{i}g(i) &\iff g(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i) \end{aligned}\]广义容斥原理（无敌对称的柿子）
\[f(n)=\sum_{i=n}^N(-1)^i\binom{i}{n}g(i) \iff g(n)=\sum_{i=n}^N(-1)^i\binom{i}{n}f(i) \]证明
咕咕咕。
广义容斥原理（较前者更常用）
\[f(n)=\sum_{i=n}^N\binom{i}{n}g(i) \iff g(n)=\sum_{i=n}^N(-1)^{i-n}\binom{i}{n}f(i) \]证明
设 \(h(i)=(-1)^ig(i)\)。
啊啊啊与更常用容斥原理证明太相似了，不赘述了。
多元的情况
我们拿二元举例子：
\[\begin{aligned} f(n,m)&=\sum_{i=0}^n\sum_{j=0}^m(-1)^{i+j}\binom{n}{i}\binom{m}{j}g(i,j) \\ \iff g(n,m)&=\sum_{i=0}^n\sum_{j=0}^m(-1)^{i+j}\binom{n}{i}\binom{m}{j}f(i,j) \end{aligned}\]其他应该同理。
例题
第二类斯特林数
我不会，长大后再学习。（
错排
\(g(x)\) 表示 \(n\) 个位置中至多有 \(x\) 个位置放错的方案数，而 \(f(x)\) 表示恰好。
\[g(n)=n! \\ g(n)=\sum_{i=0}^{n}\binom{n}{i}f(i) \]反演
\[\begin{aligned} f(n)&=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}g(i) \\&=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}i! \\&=\sum_{i=0}^{n}(-1)^{n-i}\frac{n!}{(n-i)!} \\&=n!\sum_{i=0}^{n}\frac{(-1)^{n-i}}{(n-i)!} \\&=n!\sum_{i=0}^{n}\frac{(-1)^i}{i!} \end{aligned}\]错排通项由此诞生。
P4859 已经没有什么好害怕的了
给定 \(n\le 2000\) 长度的序列 \(a_1,\dots,a_n\) 和 \(b_1,\dots,b_n\)，\(2n\) 个元素两两不同，求排列 \(p_1,\dots,p_n\) 的个数使得（以下的 \(k\) 为原题的 \(\frac{n+k}{2}\)）：
\[\sum_{i=1}^n[a_i>b_{p_i}]=k \]
设 \(f(x)\) 表示恰好 \(x\) 组 \([a_i>b_{p_i}]\) 的 \(\{p\}\) 的方案数，显然答案为 \(f(k)\)。
而 \(g(x)\) 表示钦定 \(x\) 组…………的方案数。
钦定和至少的区别
钦定指固定某些位置满足条件，而至少只是单纯的计数。
举个例子，假设要计数值域 \(0,1\) 的 \(a_1,a_2,a_3,a_4\) 序列中 \(a_i=1\) 个数不少于 \(2\) 个的方案数。
对于 \(\{a\}=\{0,1,1,1\}\) 来说：
至少：贡献为 \(1\)，因为就一种状态。
钦定：贡献为 \(3\)，因为序列中 \(3\) 个 \(1\)，我们钦定任意 \(2\) 个为 \(1\) 都会产生贡献，所以贡献为 \(\binom{3}{2}=3\)。
显然
\[g(x)=\sum_{i=x}^n\binom{i}{x}f(i) \]二项式反演
\[f(x)=\sum_{i=x}^n(-1)^{i-x}\binom{i}{x}g(i) \\ Ans=f(k)=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}g(i) \]问题转化为求 \(g(k),\dots,g(n)\)。
首先我们可以将 \(\{a\},\{b\}\) 升序排序，由于值互不相同，所以可求 \(c_1,\dots,c_n\) 使得 \(b_{c_i}\le a_i\le b_{c_i+1}\)。
我们考虑 DP，\(dp(i,j)\) 表示 \(a\) 的前 \(i\) 个中有 \(j\) 个钦定匹配了比她小的 \(b\) 值，即有
\[dp(i,j)=dp(i-1,j)+dp(i-1,j-1)\cdot(c_i-(j-1)) \]然后 \(g(i)=dp(n,i)\cdot (n-i)!\) 就做完了。
时间 \(O(n^2)\)。
record
CF997C Sky Full of Stars
有一个 \(n\times n\) 的正方形网格，用红绿蓝三种颜色染色，求有多少种染色方案使得至少一行或一列是同一种颜色。
结果对 \(998244353\) 取模。
设 \(f(i,j)\) 表示恰好 \(i\) 行与 \(j\) 列颜色相同，而 \(g(i,j)\) 表示钦定 \(i\) 行与 \(j\) 列颜色相同。
\[g(x,y)=\sum_{i=x}^n\sum_{j=y}^n\binom{i}{x}\binom{j}{y}f(i,j) \]二项式反演
\[f(x,y)=\sum_{i=x}^n\sum_{j=y}^n(-1)^{i+j-x-y}\binom{i}{x}\binom{j}{y}g(i,j) \\ \begin{aligned} Ans&=3^{n^2}-f(0,0) \\&=3^{n^2}-\sum_{i=0}^n\sum_{j=0}^n(-1)^{i+j}g(i,j) \end{aligned} \]求 \(g(i,j)\) 要分类：
- \(i\ne 0,j\ne 0\)，此时钦定的同色行列颜色必然全部一样，即
- \(i\ne 0,j=0\)（\(i=0,j\ne 0\) 情况类似），此时这些行之间颜色可以不同，即
- \(i=j=0\)，此时自由了
我向往自由！
综上
\[\begin{aligned} Ans&=-2\sum_{i=1}^n(-1)^{i}g(i,0)-\sum_{i=1}^n\sum_{j=1}^n(-1)^{i+j}g(i,j) \\&=-2A-B \end{aligned} \\ A=\sum_{i=1}^n(-1)^{i}\binom{n}{i}3^{n(n-i)+i} \\ B=\sum_{i=1}^n\sum_{j=1}^n(-1)^{i+j}\binom{n}{i}\binom{n}{j}3^{(n-i)(n-j)+1} \]\(A,B\) 分开求（分别均使用二项式定理）
\[\begin{aligned} A&=3^{n^2}\sum_{i=1}^n(-1)^{i}\binom{n}{i}3^{-ni+i} \\&=3^{n^2}\sum_{i=1}^n\binom{n}{i}(-3^{1-n})^{i} \\&=3^{n^2}((1-3^{1-n})^{n}-1) \end{aligned}\]\[\begin{aligned} B&=3^{n^2+1}\sum_{i=1}^n\sum_{j=1}^n(-1)^{i+j}\binom{n}{i}\binom{n}{j}3^{-ni-nj+ij} \\&=3^{n^2+1}\sum_{i=1}^n(-1)^i\binom{n}{i}3^{-ni}\sum_{j=1}^n(-1)^j\binom{n}{j}3^{(i-n)j} \\&=3^{n^2+1}\sum_{i=1}^n(-1)^i\binom{n}{i}3^{-ni}\sum_{j=1}^n\binom{n}{j}(-3^{i-n})^j \\&=3^{n^2+1}\sum_{i=1}^n(-1)^i\binom{n}{i}3^{-ni}((1-3^{i-n})^n-1) \end{aligned}\]所以就 \(O(n\log n)\) 解决了。
record
P6076 [JSOI2015]染色问题
咕咕咕。