一、鸽巢原理
1.鸽巢原理
将 \((\sum\limits_{i=1}^n{p_i})-n+1\) 放入 \(n\) 个盒子，一定存在一个盒子 \(i\)，使得第 \(i\) 个盒子至少装了 \(p_i\) 个物品。
练习一
有十个数 \(a_1,a_2\dots a_{10}\) 满足 \(\forall_{1\leq i\leq10}{1\leq a_i\leq60}\)，证明能够从 \(a_i\) 中挑出两个交为空的子集，使得它们的和相等。
练习二
证明一张有超过 1 个点的简单无向图必定有两点度数相等。
练习三
证明能从任意 11 个实数中挑选出 4 个数 \(a,b,c,d\) 满足：
\((ac+bd)^2\geq\frac 1 2(a^2+b^2)(c^2+d^2)\)
二、容斥原理
二项式反演
\[F(n)=\sum\limits_{i=m}^n\dbinom ni G(i) \\ G(n)=\sum\limits_{i=m}^n(-1)^{n-i}\dbinom ni G(i) \\ F(n)=\sum\limits_{i=m}^n\dbinom im G(i) \\ G(n)=\sum\limits_{i=m}^n(-1)^{i-m}\dbinom im F(i) \]证：\(F(n)=\sum\limits_{i=m}^n\dbinom ni\sum\limits_{j=m}^i(-1)^{i-j}\dbinom ijF(j)\)
\(=\sum\limits_{j=m}^nF(j)\sum\limits_{i=j}^n\dbinom ni\dbinom ij(-1)^{i-j}\)
\(=\sum\limits_{j=m}^nF(j)\sum\limits_{i=j}^n\dbinom nj\dbinom {n-j}{i-j}(-1)^{i-j}\)
\(=\sum\limits_{j=m}^n\dbinom nj F(j)\sum\limits_{i=j}^n\dbinom {n-j}{i-j}(-1)^{i-j}\)
\(=\sum\limits_{j=m}^n\dbinom nj F(j)\sum\limits_{i=0}^{n-j}\dbinom {n-j}{i}(-1)^{i}\)
\(=\sum\limits_{j=m}^n\dbinom nj F(j)[n=j]\)
\(=F(n)\)
第二种形式证明类似。
练习四(洛谷什么时候把这道题传上去的)
有 \(n\) 个元素，问有多少种选择若干个子集的方案，使得选出的子集的交集大小恰好为 \(k\)。
\(0<k\leq n\leq10^6\)
解：直接钦定 \(i\) 个的方案数是 \(F(i)=\dbinom ni(2^{2^{n-i}}-1)\)，设答案为 \(G(i)\)，观察到
\[F(i)=\sum\limits_{j=i}^{n}{\dbinom {j}{i} G(j)} \]那么反演即可得到：
\(G(k)=\sum\limits_{i=k}^n\dbinom ik F(i)\)
\(=\sum\limits_{i=k}^n(-1)^{i - k}\dbinom ik \dbinom ni (2^{2^{n-i}}-1)\)
这样之后直接做就行了。
一句话题意：有两个序列 \({a_i},{b_i}\) 保证所有元素互不相同。你需要重排 \(b\) 序列，使得恰好有 \(k\) 个 \(i\) 满足 \(a_i>b_i\)。
\(0<k\leq n\leq2000\)
解：先将 \(a\) 序列排序。
考虑设 \(dp_{i,j}\) 表示考虑了前 \(i\) 对数，恰有 \(j\) 对 \(a_x>b_x\)，发现完全没法转移（
主要是你配大的和配小的总有一个转不了，所以你考虑只算其中一个，也就是钦定有 \(j\) 对数满足 \(a_x>b_x\)，发现这样就可以转了。
\[dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\times(cnt(a_i)-j+1) \]\(cnt(a_i)\) 表示 \(b\) 序列中比 \(a_i\) 小的数的个数。
然后设 \(f(i)\) 表示钦定了 \(i\) 对的方案数，\(g(i)\) 表示恰好 \(i\) 对的方案数。观察可得：
\((n-i)!dp_{n,i}=f(i)=\sum\limits_{j=i}^n\dbinom ji g(j)\)
\(g(k)=\sum\limits_{i=k} ^n{(-1)^{i-k}\dbinom ik(n-i)!dp_{n,i}}\)
就可以直接做了。
一句话题意：有一个 \(n\times n\) 的矩阵，将其三染色，使得至少有一行或者一列同色，问方案数。
\(n\leq10^6\)
解：直接钦定 \(i\) 行 \(j\) 列同色：
\(F(i,0)=3^{(n-i)n+i}\dbinom ni\)
\(F(0,j)=3^{(n-j)n+j}\dbinom nj\)
\(F(i,j)=3^{(n-i)(n-j)+1}\dbinom ni\dbinom nj\)
考虑恰好 \(i\) 行 \(j\) 列同色：
\(G(0,0)=3^{n^2}+\sum\limits_{i=1}^n(-1)^{n-i}\dbinom ni(F(0,i)+F(i,0))+\sum\limits_{i=1}^n\sum\limits_{j=1}^n(-1)^{2n-i-j}\dbinom i0\dbinom j0 F(i,j)\)
后面那坨东西带进去：
\(\sum\limits_{i=1}^n\sum\limits_{j=1}^n3^{n^2-ni-nj+ij+1}(-1)^{2n-i-j}\dbinom ni\dbinom nj\)
\(=3^{n^2+1}\sum\limits_{i=1}^n{3^{-ni}(-1)^{n-i}\dbinom ni\sum\limits_{j=1}^n{(3^{n-i})^{j}(-1)^{n-j}\dbinom nj}}\)
\(=3^{n^2+1}\sum\limits_{i=1}^{n}{3^{-ni}(-1)^{n-i}((3^{n-i}-1)^n-(-1)^n)}\)
然后就做完了。
练习五|斯特林数
记 \({n\brace m}\) 表示把 \(n\) 个不同的物品划分为 \(m\) 个集合构成簇的方案数（不允许空集）。
解：记 \(f_{n,m}={n\brace m}\)，再记 \(g_{n,m}\) 表示允许空集时的方案数。
容易发现 \(g_{n,m} = \frac{m^n}{m!}\)。
钦定非空集合个数，可以得到：\(g_{n,m}=\sum\limits_{i=1}^m{\binom mi f_{n,i}}\)
那么对其二项式反演可以得到：\(f_{n,m}=\sum\limits_{i=1}^m{(-1)^{m-i}\binom mi g_{n,i}}\)
带入一下就可以得到：\({n\brace m} = f_{n,m}=\sum\limits_{i=1}^m{(-1)^{m-i}\binom mi\frac {m^n}{m!}}=\sum\limits_{i=1}^m{(-1)^{m-i}\frac{m^n}{i!(m-i)!}}\)
min/max容斥
\[\max{S}=\sum\limits_{T\subseteq S}{(-1)^{|T|-1}\min{T}} \\ \max_{k_{th}}{S}=\sum_{T\subseteq S}{(-1)^{|T|-k}\binom{|T|-1}{k-1}\min{T}} \]\(min/max\) 反过来也成立。
证：\(\max\limits_{k_{th}}{S}=\sum\limits_{T\subseteq S}{(-1)^{|T|-k}\dbinom {|T|-1}{k-1}\min T}\)
\(=\sum\limits_{x\in S}x\sum\limits_{x\in T\subseteq S}{(-1)^{|T|-k}\dbinom {|T|-1}{k-1}[\min{T}=x]}\)
令 \(f(x)\) 表示 \(S\) 中大于 \(x\) 的元素构成的集合。
\(=\sum\limits_{x\in S}{x}\sum\limits_{x\in T\subseteq f(x)}{(-1)^{|T|-k}\dbinom{|T|-1}{k-1}}\)
枚举 \(|T|\):
\(=\sum\limits_{x\in S}{x\sum\limits_{l = 1}^{|f(x)|}{(-1)^{l-k}\dbinom{|f(x)|-1}{l-1}\dbinom{l-1}{k-1}}}\)
\(=\sum\limits_{x\in S}{x\sum\limits_{l=1}^{|f(x)|}{(-1)^{l-k}\dbinom {|f(x)|-1}{k-1}\dbinom{|f(x)|-k}{l-k}}}\)
\(=\sum\limits_{x\in S}{x\dbinom {|f(x)|-1}{k-1}\sum\limits_{l=1} ^{|f(x)|}{(-1)^{l-k}\dbinom {|f(x)|-k}{l-k}}}\)
易知 \(|f(x)|< k\) 时无贡献。
\(=\sum\limits_{x\in S}{x\dbinom {|f(x)|-1}{k-1}\sum\limits_{l=0}^{|f(x)|-k}(-1)^l\dbinom{|f(x)|-k}{l}}\)
\(=\sum\limits_{x\in S}{x\dbinom {|f(x)|-1}{k-1}[|f(x)|=k]}\)
\(=\max\limits_{k_{th}}{S}\)
练习六
给定三个序列 \(a_i,b_i,c_i\)，求
\[\sum\limits_{1\leq i<j\leq n}{\max{a_i+a_j,b_i+b_j,c_i+c_j}-\min{a_i+a_j,b_i+b_j,c_i+c_j}} \]\(n\leq2\times10^5\)
解：暴力拆开那个 \(max\) :
\(\max{a_i+a_j,b_i+b_j,c_i+c_j}\)
\(=\min{a_i+a_j}+\min{b_i+b_j}+\min{c_i+c_j}-\min{a_i+a_j,b_i+b_j}\\-\min{a_i+a_j,c_i+c_j}-\min{b_i+b_j,c_i+c_j}+\\\min{a_i+a_j,b_i+b_j,c_i+c_j}\)
抵消掉最后那一项，剩下的项中，只有一个的是平凡的，有两个的可以二维偏序，总复杂度就是 \(O(n\log{n})\)。
一句话题意：给 \(n\) 个元素，每次会随机选择一个，有 \(p_i\) 的概率选择第 \(i\) 个，问第一次所有元素都被选择过的期望时间。
\(1\leq n\leq20\)
解：因为 \(min/max\) 容斥都是线性运算，且期望具有线性性，所以可以直接套上期望：
\(E(\max{S})=\sum\limits_{T\subseteq S}{(-1) ^{|T|-1}E(\min{T})}\)
\(E(\min{T})\) 的含义实际上就是第一次选到 \(T\) 中元素的期望时间，可以把 \(T\) 和 \(T\) 的补集看做两个整体，那么一次选中的概率就是 \(\frac 1{\sum\limits_{x\in T}{p_x}}\)，期望时间就是其倒数 \(\sum\limits_{x\in T}{p_x}\)
然后直接带进式子里计算即可，\(O(n2^n)\)。
一句话题意：给 \(n\) 个元素，每次会随机选择一个，有 \(\frac M {p_i}\) 的概率选择第 \(i\) 个，问第一次有 \(k\) 元素被选择过的期望时间。
\(1\leq l\leq n\leq 10^3,n-10\leq k\leq n,\sum\limits_{i=1}^n{p_i}=M\leq10^4\)。
解：相当于求期望出现时间第 \(n-k\) 大，令 \(k\leftarrow n-k\)，一样的期望式子列出来：
\(E(\max\limits_{k_{th}}S)=\sum\limits_{T\subseteq S}{(-1)^{|T|-1}\dbinom {|T|-1}{k-1}\frac{m}{\sum\limits_{x\in T}p_x}}\)
直接求肯定 G。因为 \(M\leq10^4\)，所以考虑计算每一种 \(\sum\limits_{x\in T}{p_x}\) 作为分母的项的系数之和，再算答案。
考虑设 \(dp_{i,j}\) 表示前 \(i\) 个，分母和为 \(j\) 的项的系数和。
不选很好转移，选的话中间那坨组合数就不太能转的动。
考虑到 \(\dbinom {|T|-1}{k-1}=\frac{|T|-1}{|T|-k}\dbinom{|T|-2}{k-1}\)，所以我们可以在方程里及一个 \(l=|T|\)，那就可以转了：
\(dp_{i,j,l}=dp_{i-1,j,l}-\frac{l-1}{l-k}dp_{i-1,j-p_i,l-1}\)
但是这个方程是 \(O(n^2m)\) 的，显然过不了，且没用到 \(k\leq10\) 的性质。
又考虑到 \(\dbinom {|T|-1}{k-1}=\dbinom{|T|-2}{k-1}+\dbinom{|T|-2}{k-2}\)
那么只需要在方程中记 \(l=k\) 即可转移：
\(dp_{i,j,l}=dp_{i-1,j,l}+dp_{i-1,j-p_i,l-1}-dp_{i-1,j-p_i,l}\)
就可以 \(O(nmk)\) 了。
标签：ni,dbinom,limits,2024.7,sum,min,笔记,数学,dp From： https://www.cnblogs.com/JPGOJCZX/p/18336945