组合数学
基本概念
- \(a^{\underline m}\) 表示 \(a\) 的 \(m\) 次下降幂。
- \(a^{\overline m}\) 表示 \(a\) 的 \(m\) 次上升幂。
递推式
\[{n \choose m}={n-1 \choose m}+{n-1 \choose m-1} \\ \]证明：
从组合意义上推导，在 n 个人中选 m 个相当于单独考虑最后一人，若他要选，则为\({n-1 \choose m-1}\)他不选则为 \({n-1 \choose m}\)。
吸引/相伴等式
\[\frac{n \choose m}{n-1 \choose m-1}=\frac{n}{m} \\ \frac{n \choose m}{n-1 \choose m}=\frac{n}{n-m} \\ \frac{n \choose m}{n \choose m-1}=\frac{n-m+1}{m} \\ \]上指标反转
\[{n \choose m}=(-1)^m{m-n-1 \choose m} \]证明：
\[\begin{aligned} {n \choose m}=\frac{n^{\underline{m}}}{m!}&=\frac{n\times(n-1)\times (n-2)\times...\times (n-m+1)}{m!} \\ &=\frac{(-1)^m\times (-n)\times(1-n)\times...\times(m-n-1)}{m!} \\ &=\frac{(-1)^m\times (m-n-1)^{\underline{m}}}{m!} \\ &=(-1)^m{m-n-1 \choose m} \end{aligned} \]
三项式系数恒等式
\[{n \choose m}{m \choose k}={n \choose k}{n-k \choose m-k} \]等式两边拆开约分即可得证。
上指标求和
\[\sum\limits_{i=0}^{n}{i \choose m}={n+1 \choose m+1} \]证明：
从组合意义入手，相当于我从 \(n+1\) 个数中选 \(m+1\) 个数，先假设选 \(i\)，那么 \(i\) 前面还需要选 \(m\) 个数，枚举这个 \(i\)，即为答案。
也可通过微积分求导知识进行证明，这里不再详述。
练习一：
求 \(\sum\limits_{i=0}^{m}{n+i \choose i}\)
解：
\[\begin{aligned} \sum\limits_{i=0}^{m}{n+i \choose i}&=\sum\limits_{i=0}^{m}{n+i \choose n+i-i} \\ &=\sum\limits_{i=0}^{m}{n+i \choose n} \\ &={n+m+1 \choose n+1} \end{aligned} \]
下指标求和（整行）
\[\sum\limits_{i=0}^{n}{n \choose i}=2^n \]证明：
\[\begin{aligned} \sum\limits_{i=0}^{n}{n \choose i}&=\sum\limits_{i=0}^{n}{n \choose i}1^{n-i}1^i \\ &=(1+1)^n=2^n \end{aligned} \]
下指标卷积（范德蒙德卷积）
\[\sum\limits_{i=0}^k{n \choose i}{m \choose k-i}={n+m \choose k} \]证明：
从 \(n\) 个数中选 \(i\) 个数，再从 \(m\) 个数中选 \(k-i\) 个数，相当于从 \(n+m\) 个数中选 \(k\) 个数。
练习二：
求 \(\sum\limits_{i=0}^{m}{n \choose i}{m \choose i}\)
解：
\[\begin{aligned} \sum\limits_{i=0}^{m}{n \choose i}{m \choose i}&=\sum\limits_{i=0}^{m}{n \choose i}{m \choose m-i} \\ &={n+m \choose m} \end{aligned} \]
上指标卷积
\[\sum\limits_{i=0}^{n}{i \choose a}{n-i \choose b}={n+1 \choose a+b+1} \]证明：
相当于从左边 \(i\) 个中选 \(a\) 个，右边 \(n-i\) 个中选 \(b\) 个。等于从 \(n\) 个中选 \(a+b\) 个，枚举分割点 \(i\)。
练习三：
求 \(\sum\limits_{i=m}^{n}(-1)^i{n \choose i}{i \choose m}\)
解：
\[\begin{aligned} \sum\limits_{i=m}^{n}(-1)^i{n \choose i}{i \choose m}&=\sum\limits_{i=m}^{n}(-1)^i{n \choose m}{n-m \choose i-m} \\ &={n \choose m}\sum\limits_{i=m}^{n}(-1)^i{n-m \choose i-m} \\ &={n \choose m}\sum\limits_{i=0}^{n-m}(-1)^{i+m}{n-m \choose i} \\ &={n \choose m}(-1)^m\sum\limits_{i=0}^{n-m}(-1)^{i}{n-m \choose i}\times 1^{n-m-i} \\ &={n \choose m}(-1)^m 0^{n-m} \\ &=(-1)^m[n=m] \\ \end{aligned} \]
Lucas定理
\[{n \choose m}\equiv{\lfloor \frac{n}{p} \rfloor \choose \lfloor \frac{m}{p} \rfloor}{{n\bmod p}\choose {m \bmod p}}\pmod p \\ \]其中 \(p\) 为质数。
证明：
注意到 \({p \choose n}\equiv[n=p \lor n=0]\pmod p\)，
因此 \((a+b)^p\equiv a^p+b^p \pmod p\)。
对于 \(f(x)=(1-x)^n,f(x)[x^m]={n \choose m}\)。
我们现在对 \(f(x)\) 做一点变换，
\[\begin{aligned} f(x)&=(1+x)^n \\ &=(1+x)^{p\times\lfloor\frac{n}{p}\rfloor}(1+x)^{n \bmod p} \\ &=((1+x)^p)^{\lfloor\frac{n}{p}\rfloor}(1+x)^{n \bmod p} \\ \end{aligned} \]\[f(x)\equiv (1+x^p)^{\lfloor\frac{n}{p}\rfloor}(1+x)^{n \bmod p} \pmod p \]所以对于 \(f(x)\)，前半部分 \(((1+x)^p)^{\lfloor\frac{n}{p}\rfloor}\) 一定为 \(p\) 的倍数，后半部分 \((1+x)^{n \bmod p}\) 一定小于 \(p\) ，设 \(h(x)=(1+x^p)^{\lfloor\frac{n}{p}\rfloor}\) ， \(g(x)=(1+x)^{n \bmod p}\)。
\(f(x)[x^m]=h(x)[x^{kp}]\times g(x)[x^{r}] \pmod p\)
所以就有 \(m=kp+r\rightarrow k=\lfloor \frac{m}{k}\rfloor，r=m\bmod p\)。
就可以得出：
\[{n \choose m}\equiv{\lfloor \frac{n}{p} \rfloor \choose \lfloor \frac{m}{p} \rfloor}{{n\bmod p}\choose {m \bmod p}}\pmod p \\ \]
二项式定理
\[(x+y)^n=\sum\limits_{i=0}^{n}{n \choose i}x^{n-i}y^i \]拓展——下降（上升）幂二项式定理
\[(x+y)^{\underline{n}}=\sum\limits_{i=0}^{n}{n \choose i}x^{\underline{n-i}}y^{\underline{i}} \\ (x+y)^{\overline{n}}=\sum\limits_{i=0}^{n}{n \choose i}x^{\overline{n-i}}y^{\overline{i}} \\ \]证明（这里不用数学归纳法进行证明）：
\[\begin{aligned} \sum\limits_{i=0}^{n}{n \choose i}x^{\overline{n-i}}y^{\overline{i}}&=\sum\limits_{i=0}^{n}\frac{n!}{(n-i)!i!}x^{\overline{n-i}}y^{\overline{i}} \\\\ &=\sum\limits_{i=0}^{n}n!\frac{x^{\overline{n-i}}y^{\overline{i}}}{(n-i)!i!} \\ &=n!\sum\limits_{i=0}^{n}{x \choose i}{y \choose n-i} \\ （\text{根据范德蒙德卷积})&=n!{x+y \choose n} \\ &=(x+y)^{\underline{n}} \\ \end{aligned} \]上升幂方法相同。
错排
定义：一个满足 \(a_i\ne i\) 的序列。
推导式：
\[f_n=(n-1)(f_{n-1}+f_{n-2}) \]证明：
若当前将 \(1\) 放到位置 \(k(k\ne 1)\)，那么 \(k\) 的放置位置可以分类讨论：
\(k\) 放在位置 \(1\) 上，那么还会剩下 \(n-2\) 个数错排，方案数为 \(f_{n-2}\)。
\(k\) 放到某个位置 \(t(t\ne 1)\)，那么假设 \(1\) 号位置填上了 \(P\)，则 \(p\ne 1 \land p\ne k\)，此时可以考虑一个新序列，把 \(1\) 去掉，此时方案数为 \(f_{n-1}\)
设 \(\text{cyc}_\pi\) 将长为 \(n\) 的排列 \(\pi\) 当成置换时所能分解成的循环个数。给定两个整数 \(n,k\) 和一个 \(k-1\) 次多项式，对 \(1\leq m\leq n\) 求：
\[\sum\limits_{\pi}F(\text{cyc}_{\pi}) \]其中 \(\pi\) 是长度为 \(m\) 且不存在位置 \(i\) 使得 \(\pi_i=i\) 的排列。
解：
\[\begin{aligned} \sum\limits_{\pi}F(cyc_\pi)&=\sum\limits_\pi\sum\limits_{i=0}^{k-1}f_i\times cyc_\pi^i \\ &=\sum\limits_\pi\sum\limits_{i=0}^{k-1}\sum\limits_{j=0}^{i-1} f_i{i \brace j}{cyc_\pi \choose j}j! \\ &=\sum\limits_{j=0}^{k-1}j!\sum\limits_{i=j}^{k-1}f_i {i \brace j}\sum\limits_\pi{cyc_\pi \choose j} \end{aligned} \]我们发现，\(\sum\limits_{i=j}^{k-1}f_i {i \brace j}\) 与 \(\sum\limits_\pi{cyc_\pi \choose j}\) 无关，所以可以将其预处理。
\(j!，f_i，{i \brace j}\) 都是能够优先处理的。现在考虑 \({cyc_\pi \choose j}\) 的处理。
定义函数 \(C_{t,j}\) 为长度为 \(t\) ，环数为 \(j\) 的排列数，\(P_{t,j}=\sum\limits_{{|\pi |}=t}{cyc_\pi \choose j}\) ，通过推导，能够得出：
\[\begin{aligned} C_{t,j}&=(n-1)(C_{t-1,j}+C_{t-2,j-1}) \\ P_{t,j}&=(n-1)(P_{t-1,j}+P_{t-2,j-1}+P_{t-1,j-1}) \end{aligned} \]那么答案即为：
\[\begin{aligned} \sum\limits_{j=0}^{k-1}j!\sum\limits_{i=j}^{k-1}f_i {i \brace j}\sum\limits_{k=1}^nP_{i,j} \end{aligned} \]其中 \(i\) 的复杂度为 \(O(n)\) ，\(j\) 的复杂度为 \(O(k)\)，总复杂度为 \(O(nk)\)，不会超时。
鸽巢定理
原理：将 \((\sum\limits_{i=1}^{n}p_i)-n+1\) 个东西放入 \(n\) 个盒子中，一定存在一个盒子 \(i\)，使得第 \(i\) 个盒子至少装了 \(p_i\) 个物品。
证明（反证法）：
\[\forall x\in \mathbb{N^* } \land 1\le x \le n,a_i<p_i \\ \sum a_i<(\sum p_i)-n<(\sum p_i)-n+1 \]与条件矛盾，故成立。
练习四
有十个数 \(a_1,a_2...a_10\) 满足 \(\forall_{1\le i\le 10}1\le a_i\le 60\)，证明能够从 \(a_i\) 中挑出两个交为空的子集，使得它们的和相等。
证明：
两个交为空的子集和相等，所以加上交集后和仍不变，总共有 \(2^{10}=1024\)，但值域仅为 \([0,600]\)，故能够选出。
练习五
证明一张有超过 \(1\) 个点的简单无向图必定有两点度数相等。
证明：
考虑分类讨论：
有 \(2\) 个度数为 \(0\) 的点，符合条件。
有 \(1\) 个度数为 \(0\) 的点，则第 \(n\) 个点需要连 \(n-1\) 条边，故至少有一个点符合。
没有度数为 \(0\) 的点，那么边数的范围为 \([1,n-1]\)，所以符合。
练习六
证明能从任意 11 个实数中挑选出 4 个数 \(a,b,c,d\) 满足：
\((ac+bd)^2\geq\frac 1 2(a^2+b^2)(c^2+d^2)\)
证明：
我们令 \(\overrightarrow x=(a,b),\overrightarrow y=(c,d)\)。原式变为：\(\overrightarrow x \overrightarrow y \ge \frac{\sqrt{2}}{2}\sqrt{|\overrightarrow x||\overrightarrow y|}\)。那么就有：\(\cos<\overrightarrow x,\overrightarrow y>=\frac{\overrightarrow x \overrightarrow y}{\sqrt{|\overrightarrow x||\overrightarrow y|}} \ge \frac{\sqrt{2}}{2}\)
故 \(\overrightarrow x\) 与 \(\overrightarrow y\) 的夹角为 \(45\) 度。然后我们发现，\(11\) 个实数中必定有至少 \(6\) 个正数或负数，故我们只需选择正负性相同的 \(4\) 个数字，这样两条向量一定在同一象限。因为我们有在同一象限的 \(3\) 条向量，每两条之间最大夹角小于 \(45\) 度。故得证。
容斥原理
对于一个集合 \(S\) 的一部分子集构成的簇 \(P\) 有：
\[|\bigcup\limits_{T\in P}T|=\sum\limits_{Q \sub P}(-1)^{|Q|-1}|\bigcap\limits_{T \in Q}T| \]基本容斥原理为高中必学内容，这里对此不过多阐述。
二项式反演
结论：
\[F(n)=\sum\limits_{i=m}^{n}{n \choose i}G(i) \\ G(n)=\sum\limits_{i=m}^{n}(-1)^{n-i}{n \choose i} F(i) \\ F(n)=\sum\limits_{i=m}^{n}{i \choose m}G(i) \\ G(n)=\sum\limits_{i=m}^{n}(-1)^{i-m}{i \choose m} 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 \le n \le 10^6\)
解：
我们先考虑子集的交集大小至少为 \(i\) 的方案，记为 \(F(i)\)，那么相当于先挑出 \(i\) 个，再从 \(n-i\) 个中计算出剩余元素的子集的数量即为 \(2^{n-i}\)，然后我们需要在这些剩余子集中的挑选子集方案，即为 \(2^{2^{n-i}}\)，考虑到当剩余子集为空时，方案就为 \(i\) ，舍去，所以可得 \(F(i)={n \choose i}(2^{2^{n-i}}-1)\)。
然后我们考虑答案函数 \(G(k)\)，因为 \(F(i)\) 在求解时会对所有交集大小大于等于 \(i\) 的情况计数，理想情况下应该计数 \(1\) 次，但是经过画图可以发现，当我们处理类似 \(G(i+1)\) 的情况时，其也会对 \(F(i)\) 产生贡献，贡献为 \({i+1 \choose i}\)，所以可以得出结论：
\[F(i)=\sum\limits_{j=i}^{n}{j \choose i}G(j) \]进行二项式反演可得：
\[\begin{aligned} G(k)&=\sum\limits_{i=k}^{n}{i \choose k}(-1)^{i-k}F(i)\\ &=\sum\limits_{i=k}^{n}(-1)^{i-k}{i \choose k}{n \choose i}(2^{2^{n-i}}-1) \end{aligned} \]现在就可以解决了。
练习八 BZOJ3622 已经没有什么好害怕的了（P4859）
有两个序列 \(a_i,b_i\) 保证所有元素互不相同。你需要重排 \(b\) 序列，使得恰好有 \(k\) 个 \(i\) 满足 \(a_i>b_i\)。，求方案数。
\(0<k\leq n\leq2000\)。
解：
先将 \(a\) 序列排序，使其单调上升。
考虑 \(dp_{i,j}\) 表示考虑前 \(i\) 对数，恰有 \(j\) 对 \(a_i>b_i\) ，这样无法转移。
还是先考虑前 \(i\) 个中至少 \(j\) 对 \(a_i>b_i\)，设为 \(dp_{i,j}\)，那么就有
\[dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}*(cnt(a_i)-j+1) \]\(cnt(a_i)\) 表示在当前 \(i\) 位置，有多少个 \(b\) 满足 \(a_i>b\)。
然后设 \(F(i)\) 表示钦定 \(i\) 对符合条件的方案数，\(G(i)\) 表示恰好 \(i\) 对的方案数。在当前位置，由于钦定 \(i\) 对符合，所以剩下的数随便排序，就为 \(A_{n-i}^{n-i}=(n-1)!\)，就有：
\[(n-i)!dp_{n,i}=F(i)=\sum\limits_{j=i}^{n}{j \choose i}G(j) \]反演可得：
\[\begin{aligned} G( k)&=\sum\limits_{i=k}^{n}{i \choose k}(-1)^{i-k}F(i) \\ &=\sum\limits_{i=k}^{n}{i \choose k}(-1)^{i-k}(n-i)!dp_{n,i} \end{aligned} \]然后就能够解决啦。
有一个 \(n\times n\) 的矩阵，将其三染色，使得至少有一行或者一列同色，问方案数。
\(n\leq10^6\)
解：
我们先钦定有 \(i\) 行 \(j\) 列同色，记为 \(F(i,j)\)
\[F(i,j)= \begin{cases} 3^{(n-i)n+i}{n \choose i} & j=0 \\ 3^{(n-j)n+j}{n \choose j} & i=0 \\ 3^{(n-i)(n-j)+1}{n \choose i}{n \choose j} & i\ne 0,j\ne 0 \\ \end{cases} \]考虑恰好有 \(i\) 行 \(j\) 列同色，记为 \(G(i,j)\)
我们需要求至少一行一列，所以可以用 \(全集-G(0,0)\)。
\[F(x,y)=\sum\limits_{i=x}^{n}\sum\limits_{j=y}^{n}{i \choose x}{j \choose y}G(i,j) \\ G(x,y)=\sum\limits_{i=x}^{n}\sum\limits_{j=y}^{n}(-1)^{i+j-x-y}{i \choose x}{j \choose y}F(i,j) \\ \\ G(0,0)=3^{n^2}+\sum\limits_{i=1}^{n}(-1)^{n-i}{n \choose i}(F(0,i)+F(i,0))+\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}(-1)^{2n-i-j}{n \choose i}{n \choose j}F(i,j) \\ G(0,0)=3^{n^2}+\sum\limits_{i=1}^{n}(-1)^{n-i}{n \choose i}(F(0,i)+F(i,0))+\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}(-1)^{i+j}{n \choose i}{n \choose j}F(i,j) \]将 \(F(i,j)\) 代入原式子。后面那坨东西即为：
\[\begin{aligned} &=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}(-1)^{i+j}{n \choose i}{n \choose j}3\times 3^{(n-i)(n-j)} \\ &=3^{n^2+1}\sum\limits_{i=1}^{n}{n \choose i}(-1)^i3^{-in}\sum\limits_{j=1}^{n}{n \choose j}(-1)^j3^{-jn}3^{ij} \\ \end{aligned} \]现在发现 \(3^{ij}\) 是最不好处理的，因为它使得不能使用二项式定理，先考虑这个的处理方法。
\[\begin{aligned} &=3^{n^2+1}\sum\limits_{i=1}^{n}{n \choose i}(-1)^i3^{-in}\sum\limits_{j=1}^{n}{n \choose j}(-1)^j3^{j(i-n)} \\ &=3^{n^2+1}\sum\limits_{i=1}^{n}{n \choose i}((-1)^i3^{-in}(1-3^{(i-n)})^n-1) \\ G(0,0)&=3^{n^2}+\sum\limits_{i=1}^{n}(-1)^{n-i}{n \choose i}(F(0,i)+F(i,0))+(-1)^i3^{-in}\sum\limits_{j=1}^{n}{n \choose j}(-1)^j3^{-jn}3^{ij} \end{aligned} \]现在就可以处理了。
练习十（第二类斯特林数通项求法）
记 \({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}{m \choose i}F(n,i)。\)
进行反演可得：\(F(n,m)=\sum\limits_{i=1}^{m}{m \choose i}(-1)^{m-i}G(n,i)。\)
代入可得：\({n\brace m} = f_{n,m}=\sum\limits_{i=1}^m{(-1)^{m-i}\binom mi\frac {i^n}{i!}}=\sum\limits_{i=1}^m{(-1)^{m-i}\frac{i^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\)：
\[\begin{aligned} &\ \ \ \ \max a_i+a_j,b_i+b_j,c_i+c_j \\ &=a_i+a_j+b_i+b_j+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} \end{aligned} \]最后一项与原式抵消掉，剩下的两种 \(min\) 中，第一种可以直接求出，第二种可以化成以下形式：
\[\min(a,b)=a[a<b] \]所以可以变成：
\[-a_i-a_j[a_i+a_j<b_i+b_j]-a_i-a_j[a_i+a_j<c_i+c_j]-b_i-b_j[b_i+b_j<c_i+c_j] \\ -a_i-a_j[a_i-b_i<b_j-a_j]-a_i-a_j[a_i-c_i<c_j-a_j]-b_i-b_j[b_i-c_i<c_j-b_j] \]这个实质就是求顺序对（二位偏序），总复杂度 \(O(n \log n)\)。
练习十二
给 \(n\) 个元素，每次会随机选择一个，有 \(p_i\) 的概率选择第 \(i\) 个，问第一次所有元素都被选择过的期望时间。
\(1\leq n\leq20\)
解：
设每个元素被选择时的时间为 \(t_i\)，那么所有元素被选就是 \(t_{maxS}\)，套上公式：
\[E(\max{S})=\sum\limits_{T\subseteq S}{(-1) ^{|T|-1}E(\min{T})} \\ \]\(E(\min T)\) 的含义实际上就是第一次选到 \(T\) 中元素的期望时间，一次选中的概率是 \(\frac{1}{\sum\limits_{x\in T}p_x}\) ，期望时间就是其倒数 \(\sum\limits_{x\in T}p_x\)
然后套入式子计算即可，\(O(n2^n)\)。
给 \(n\) 个元素，每次会随机选择一个，有 \(\frac {p_i} M\) 的概率选择第 \(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\)。
解：
标签：frac,组合,limits,sum,数学,choose,aligned,dbinom From： https://www.cnblogs.com/lizihan00787/p/18323230相当于就是求 \(t_i\) 第 \(k\) 小，思路大体上与上一题差不多，我们不妨改成求 \(n-k\) 大，让 \(k=n-k\)，就能得出式子：
\[\begin{aligned} E(\max\limits_{k_{th}}S)&=\sum\limits_{T\sube S}(-1)^{|T|-k}E(\min T) \\ &=\sum\limits_{T\sube S}(-1)^{|T|-k}{|T|-1 \choose k-1}\frac{M}{\sum\limits_{x\in T}p_x} \end{aligned} \]现在麻烦的是 \(\frac{M}{\sum\limits_{x\in T}p_x}\)，我们发现所有 \(p_i\) 之和不会超过 \(M\)，所以可以考虑计算每一种 \(\sum\limits_{x\in T}p_x\) 作为分母的项的系数之和。考虑设 \(dp_{i,j}\) 表示前 \(i\) 个，分母和为 \(j\) 的项的系数和。
在转的时候会发现转不了，所以再设一个参数 \(l=|T|\)。
那么就有 \({|T|-1 \choose k-1}=\frac{|T|-1}{|T|-k}{|T|-2 \choose k-1}\) 。
\[dp_{i,j,l}=dp_{i-1,j}-\frac{l-1}{l-k}dp_{i-1,j-p_i,l-1} \]这个复杂度过不了，所以换方法，因为 \({|T|-1 \choose k-1}={|T|-2 \choose k-1}+{|T|-2 \choose k-2}\)，所以：
\[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)\) 的了。