寒假的第一天在颓组合数学中度过 
组合数的性质
$1.1$
$$\binom{n}{m} = \binom{n}{n-m}$$
考虑从$n$个物品里选$m$个物品的方案数和从$n$个物品里选$n-m$个物品扔掉的方案数是一样的。
$1.2$
$$\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}$$
考虑从$n$个物品里选$m$个物品的方案数有两种情况转移过来，一种是当前物品不选，那么就是从剩下的$n-1$个物品里选$m$个物品，另一种是选择当前物品，那么就是从剩下的$n-1$种物品里选择$m-1$个物品。
$1.3$
$$\sum_{i=0}^n \binom{m+i}{i} = \binom{m+n+1}{n}$$
根据$1.2$，有$\binom{m}{0} = \binom{m+1}{0}$，所以原式变为
$$\binom{m+1}{0} + \binom{m+1}{1} + \binom{m+2}{2} + \cdots + \binom{m+n}{n}$$
$$\binom{m+2}{1} + \binom{m+2}{2} + \cdots + \binom{m+n}{n}$$
以此类推，将它们两两合并，最后结果就是$\binom{m+n+1}{n}$。
$1.4$
$$\sum_{i=0}^n \binom{n}{i} = 2^n$$
根据二项式定理，有
$$(1+1)^n = \sum_{i=0}^n \binom{n}{i} 1^i 1^{n-i}$$
$$(1+1)^n = \sum_{i=0}^n \binom{n}{i}$$
$$2^n = \sum_{i=0}^n \binom{n}{i}$$
$1.5$
$$\sum_{i=0}^n \binom{n}{i} x^i = (x+1)^n$$
这也是从二项式定理搞过来的
$$(x+1)^n = \sum_{i=0}^n \binom{n}{i} x^i 1^{n-i}$$
$$(x+1)^n = \sum_{i=0}^n \binom{n}{i} x^i$$
$1.6$
$$\sum_{i=0}^n (-1)^i \binom{n}{i} = 0$$
其实就是$1.5$的变形，当$x=-1$的时候。
$1.7$
$$\binom{n}{m} \times \binom{m}{r} = \binom{n}{r} \times \binom{n-r}{m-r}$$
根据定义式将式子展开，可得
$$\frac{n!}{m! \times (n-m)!} \times \frac{m!}{r! \times (m-r)!}$$
约去$m!$，同时乘$(n-r)!$，再把$(n-m)!$和$r!$交换位置，可得
$$\frac{n!}{(n-r)! \times r!} \times \frac{(n-r)!}{(n-m)! \times (m-r)!}$$
也就是
$$\binom{n}{r} \times \binom{n-r}{m-r}$$
我们还可以考虑按定义推导，原式计数的是从$n$个元素中选$m$个元素，再从$m$个元素中选$r$个元素的数量，那么我们可以先选出$r$个元素，再考虑有多少个集合包含了它，也就是从剩下的$n-r$个元素中再选$m-r$个。
$1.8$
$$\sum_{i=0}^{n/2} \binom{n}{2i} = \sum_{i=0}^{n/2} \binom{n}{2i+1} = 2^{n-1}$$
根据$1.6$，有
$$\sum_{i=0}^{n/2} \binom{n}{2i} = \sum_{i=0}^{n/2} \binom{n}{2i+1}$$
根据$1.4$，有
$$\sum_{i=0}^{n/2} \binom{n}{2i} + \sum_{i=0}^{n/2} \binom{n}{2i+1} = 2^n$$
所以，有
$$\sum_{i=0}^{n/2} \binom{n}{2i} = \sum_{i=0}^{n/2} \binom{n}{2i+1} = 2^n \div 2=2^{n-1}$$
$1.9$
$$\binom{n+m}{r} = \sum_{i=0}^r \binom{n}{i} \times \binom{m}{r-i}$$
根据组合数的定义，在$n+m$个数中选$r$个的方案数等于枚举在$n$个元素中选几个，剩下的在$m$个元素中选。
特别的，当$n=m=r$时，有
$$\binom{2n}{n} = \sum_{i=0}^n \binom{n}{i} \binom{n}{n-i} = \sum_{i=0}^n\binom{n}{i} \times \sum_{i=0}^n \binom{n}{i} =\sum_{i=0}^n \binom{n}{i}^2$$
$1.10$
$$m \times \binom{n}{m} = n \times \binom{n-1}{m-1}$$
根据定义式将式子拆开，有
$$m \times \frac{n!}{m! \times (n-m)!}$$
将$m$和分母中的$m!$约分，再将分子里的$n!$中拆一个$n$出来，得到
$$n \times \frac{(n-1)!}{(m-1)! \times (n-m)!}$$
$1.11$
$$\sum_{i=1}^n \binom{n}{i} \times i = n \times 2^{n-1}$$
还是按照定义式展开，并将$i$乘进去，可得
$$n \sum_{i=1}^n \frac{(n-1)!}{(i-1)! \times (n-i)!}$$
也就是
$$n \sum_{i=1}^n \binom{n-1}{i-1}$$
用$i-1$代替$i$,得
$$n \sum_{i=0}^{n-1} \binom{n-1}{i}$$
也就是
$$n \times 2^{n-1}$$
$1.12$
$$\sum_{i=1}^n \binom{n}{i} \times i^2 = n \times (n+1) \times 2^{n-2}$$
也同样按定义式拆开，将$i$乘进去，得到
$$n \sum_{i=0}^{n-1} \binom{n-1}{i} \times (i+1)$$
$$= n \sum_{i=0}^{n-1} \binom{n-1}{i} + n \sum_{i=0}^{n-1} \binom{n-1}{i} \times i$$
$$= n \times 2^{n-1} + n \times (n-1) \times 2^{n-2}$$
$$= n \times 2^{n-2} \times (n+2-1)$$
$$= n \times (n+1) \times 2^{n-2}$$
$1.13$
$$\sum_{i=k}^n \binom{i}{k} = \binom{n+1}{k+1}$$
把$1.2$式带进去就好了。
广义莫比乌斯反演
经典莫比乌斯反演
$\phi \ast 1=id$ 的证明
$$\phi(p^k)\ast1$$
$$=\sum_{d|p^k}\phi(d)$$
$$=\sum_{i=0}^k\phi(p^i)$$
$$=\sum_{i=0}^k(p^i-p^{i-1})$$
$$=p^k$$
$$Q.E.D.$$
由于$\phi \ast 1$是积性函数，所以$\phi \ast 1(n)=\prod_{i=1}^k\phi \ast 1(pi)=\prod_{i=1}^kpi=id$,所以$\phi \ast 1=id$
子集反演
对于两个函数$F(S)$和$G(S)$
$$F(S)=\sum_{T\subseteq S}G(T)$$
那么我们可以得出
$$G(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}F(T)$$
$$G(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}F(T)$$
$$=\sum_{T\subseteq S}(-1)^{|S|-|T|}\sum_{U\subseteq T}G(U)$$
$$=\sum_{U\subseteq S}G(U)\sum_{U\subseteq T \subseteq S}(-1)^{|S|-|T|}$$
通过枚举$|T|-|U|$的元素个数即
$$|T|=|U|+i$$
$$=\sum_{U\subseteq S}G(U)\sum_{i=0}^{|S|-|U|}\binom{|S|-|U|}{i}(-1)^{|S|-|U|-i}$$
然后喜闻乐见的发现了一个二项式定理
$$=\sum_{U\subseteq S}G(U)0^{|S|-|U|}$$
当$|S|=|U|$时,带进原式我们惊奇的发现后面这玩意
$$=(-1)^{|S|-|U|}=1$$
$$=\sum_{U\subseteq S}G(U)[U=S]$$
$$=G(S)$$
$$Q.E.D.$$
杜教筛
杜教筛的离散化：因为每一次传进去的参数如果$<\sqrt n$，就直接调用预处理出来的数据，如果$>\sqrt n$就进行记忆化，因为都$> \sqrt n$，而且每个数都可以被表示成$n/x$的形式，那么对于每个n都有不同的x那么就可以把这个存进不同的x里面，开一个$\sqrt n$的数组就行。
但是如果n变化了显然$n/x$就不一样了，那么就要全部清空
如果有两个参数$n$和$m$,那么也不能这样离散化，因为每次对于$n/i$相等的一段区间可能会进行多次杜教筛计算，同一段表示成$n/x$中的x都是相同的，这样同一段都会被存进同一个$x$里面，这样就会产生冲突
$min-max$容斥
设$max(S)$表示集合$S$中的最大值，$min(S)$表示集合$S$中的最小值，那么可以这样反演
$$max(S) = \sum_{T \subseteq S} (-1)^{\left| T \right| -1} min(T)$$
$$min(S) = \sum_{T \subseteq S} (-1)^{\left| T \right| -1} max(T)$$
由于求$min$和求$max$类似，所以以下只对求$max$进行讨论。
考虑设$f(\left| T \right|)$为反演系数，针对集合中所有元素中第$x+1$大的元素，用$num(x+1)$表示其出现次数，考虑该元素在多少个集合里产生了贡献，有
$$num(k+1) = \sum_{i=0}^k \binom{k}{i} \times f(k+1)$$
二项式反演，得
$$num(k+1) = \sum_{i=0}^k \binom{k}{i} \times f(k+1)$$
当要求集合中最大的元素时,只有最大值的元素出现次数为$1$，其它元素出现次数都为$0$,所以有
$$[k==0] = \sum_{i=0}^k \binom{k}{i} \times f(k+1)$$
二项式反演，得
$$f(k+1) = \sum_{i=0}^k (-1)^{k-i} \binom{k}{i} \times [i==0]$$
所以对于一个大小为$x$的集合来说,其反演系数为
$$f(k)=(-1)^{k-1}$$
如果我们仔细观察一下推导过程，就会发现我们不仅能求最大和最小值，还能求第$x$大值。
转到对容斥系数的证明
$$num(k+1) = \sum_{i=0}^k \binom{k}{i} \times f(k+1)$$
当求第$x$大值的时候，只有$num(x)$为$1$，其它都为$0$,所以有
$$[k==x-1] = \sum_{i=0}^k \binom{k}{i} \times f(k+1)$$
二项式反演，有
$$f(k+1) = \sum_{i=0}^k (-1)^{k-i} \binom{k}{i} \times [i==x-1]$$
$$f(k) = (-1)^{k-x} \times \binom{k-1}{x-1}$$
所以得到求第$x$大的$min-max$容斥式子
$$kthmax(S) = \sum_{T \subseteq S} (-1)^{\left| T \right| -x} \times \binom{\left| T \right| -1}{x-1} min(T)$$
