组合数学

组合计数

常用公式：

1.${N \choose K}=N!/(K!*(N-K)!)$

2.$\sum_{i=0}^{N}{N \choose I}=2^N$

3.$\sum_{i=0}^{N}{N\choose i}(-1)^i=0$

4.$\sum_{N}^{i=0}{N\choose i}x^i=(1+x)^N$

5.范德蒙公式：$\sum_{i=0}^{K}{N\choose i}{M\choose K-i}={N+M\choose K}$

6.重要：${N\choose K}{K\choose i}={N\choose i}{N-i\choose K-i}$

理解：N个里选出来K个，再从K个之中选出i个，就相当于是在我的N中先选出来i个，再从剩下的N-i个之中选出来K-i个

经典场景：$\sum_k\sum_if(i){N\choose K}{K\choose i}=\sum_if(i)\sum_K{N\choose i}{N-i\choose K-i}=\sum_if(i){N\choose i}2^{N-i}$

7.帕斯卡公式：${N\choose i}={N-1\choose i-1}+{N-1\choose i}$

然后就可以推出来：${N+1\choose K+1}=\sum_{i=K}^{N}{i\choose K}$

等价的： ${N+1\choose K+1}=\sum_{i=K}^{N}{i\choose i-K}$ （要对这个公式敏感一点）

这个公式有一个巧记的方法：

我枚举一个i，想象我选的第一个数是第i个，那么我还剩下N-i个物品，我要在这N-i个物品中选取K个，根据加法原理进行加和，就得出了这一个公式

另一种利用：$\sum_{i=0}^{K}{N+1\choose i}=\sum_i{N\choose i}+{N\choose i-1}=2\sum_{i=0}^{K}{N\choose i}-{N\choose K}$

可以运用杨辉三角形进行理解：上一行的所有数都向下产生了两倍于自己的贡献值，除了最后一个之外，所以我乘以二再减去末尾

似乎是另一种变形：$\sum_{k<=n}{r+k\choose k}={r\choose 0}+{r+1\choose 1}+···+{r+n\choose n}={r+n+1\choose n}$，其实相当于上面的那个等价帕斯卡公式

另一种名字叫做关于上指标求和，$\sum_{0<=k<=n}{k\choose m}={n+1\choose m+1},m,n>=0$

这两个个已通过对称性进行相互推出

8.重要的一个东西：二项式定理：$(x+y)^r=\sum_{k}{r\choose k}x^ky^{r-k}$整数r>=0或者$|x/y|<1$

这个东西的很多特殊值是非常有用的比如1+1,1+(-1)一类的，可以用来推式子(比如容斥呀容斥呀容斥呀什么的……)

上面前几条性质都是二项式定理的特殊值，所以二项式定理还是很好用的……

推论：$0^n={n\choose 0}-{n\choose 1}+…+(-1)^n{n\choose n},n>=0$ (有一道题告诉我：同一行的（也就是上指标一样的）奇数二项式之和等于偶数二项式之和)（洛谷P5390数学作业，一个小绿题我做了老半天做不出来太恶心了）题目

9. 负数二项式：对于取负数值的n和取正数值的n，其${n\choose k}$之间有一种联系，一般的规则是：

$${r\choose k}=(-1)^k{k-r-1\choose k}$$

我们称之为：反转上指标

10. lucas定理

（我竟然把lucas放到了第十个）

对于p是质数的情况

$${n\choose m}\bmod p={n\bmod p\choose m\bmod p}*({n/p\choose m/p})\bmod p$$

证明的过程我确实是不会。。。 （听说要用到生成函数知识）（以后再说）

lucas定理其实直接背过就可以了不需要理解 因为根本理解不了

既然有了p是质数的情况，那么就应该有p不是质数的情况了吧：

扩展lucas定理横空出世但是其实它和lucas定理没有任何的关系

我们在学习数论的时候是知道了一个东西叫做中国剩余定理的（简称韩信点兵小学奥数）

那么我们可以把p分解质因数，（由唯一分解定理

那么我们一定可以把p分解成若干个质数的多少次方相乘的形式

比如：$p={p_1}^{c_1} * {p_2}^{c_2} * … * {p_k}^s{c_k}$

那么我们求出${n\choose m}\bmod {p_1} ^ {c_1}$以及剩下的p2,p3…啊自用中国剩余定理合并一下就可以

但是在求得时候我们应该怎么求出来每一个式子呢？

我们把${n\choose m}$中$m!$，$(n-m)!$，$n!$中包含着$p_1$的项提出来，我们假设x为n！中是$p_1$的倍数的项，然后把它们提出来，变成这个样子：

$${n\choose m}\bmod{p_1}^{c_1} = \dfrac{\dfrac{n!}{ {p_1} ^ {x} } } {\dfrac{m! } { {p_1} ^ {y} }\dfrac{n-m!}{ {p_1 } ^ { z } } } * { p_1 } ^ { x-y-z } \bmod { p_1 } ^ { c_1 }$$

就是把n！，m！和n-m！中p1的倍数全部都提取出来

那么这个xyz怎么求呢？

首先我们可以知道n以内的p的倍数总共有floor(n/p)个，但是n以内也有$p^2,p^3,p^4…$的倍数

我们是需要把另外的p因子提出来，那么我们还需要求一遍n以内$p^2$的倍数，然后加上（因为之前已经加上了p的倍数，加过一次了，但是这些数字中含有两个p，就需要再加一次就够了（三次方四次方都一样

那么我们算出来的这个式子有什么用呢？用处大了

既然我们把所有的p都提出来了，那么下面的东西就都互质了，就可以求逆元了

（就可以算了

那么我们还得考虑一下我们化简出来的这个式子的阶乘怎么算。。。

我们考虑这么一件事情：

p的倍数一定不和它互质，但是……只要不是p的倍数就一定不和他互质

那么我们可以发现一个规律就是，在我们求出来p-1的阶乘之后，p+1,p+2…2p-1这些数字在mod p的意义上是和1-p-1相同的，那么这就是一个循环的东西，就有规律。那么在最后的地方会剩下一点没有处理到的，特判一下就可以了

听 说 扩 展 Lucas 基 本 上 没 考 过 所 以 我 们 大 家 不 要 学 它!

想 知 道 为 什 么 在 末 尾 才 说 他 不 考 吗 ， 显 然 是 故 意 的 吧 /xyx

我们来直接梳理一下常用的组合恒等式：

$$\binom{n}{k} = \dfrac{n!}{k!(n-k)!}\\ \binom{n}{k} = \binom{n}{n-k}\\ \binom{r}{k} = \dfrac{r}{k}\binom{r-1}{k-1}\\ \binom{r}{k} = \binom{r-1}{k}+\binom{r-1}{k-1}\\\ \binom{r}{k} = (-1)^k\binom{k-r-1}{k}\\ \binom{r}{m}\binom{m}{k} = \binom{r}{k}\binom{r-k}{m-k}\\ \sum_k\binom{r}{k}x^ky^{y-k} = (x+y)^r\\ \sum_{r\le n}\binom{r+k}{k} = \binom{r+n+1}{n}\\ \sum_{0\le k\le n}\binom{k}{m} = \binom{n+1}{m+1}\\ \sum_k\binom{r}{k}\binom{s}{n-k} = \binom{r+s}{n}\\ \sum_k\binom{r}{m+k}\binom{s}{n-k} = \binom{r+s}{m+n}\\ \sum_k\binom{l}{m+k}\binom{s}{n+k} = \binom{l+s}{l-m+n}\\ \sum_k\binom{l}{m+k}\binom{s+k}{n}(-1)^k = (-1)^{l+m}\binom{s-m}{n-l}\\ \sum_{k\le l}\binom{l-k}{m}\binom{s}{k-n}(-1)^k = (-1)^{l+m}\binom{s-m-l}{l-m-n}\\ \sum_{-q\le k\le l}\binom{l-k}{m}\binom{q+k}{n} = \binom{l+q+1}{m+n+1}$$

排列组合例题：

洛谷P2183 礼物

题目链接

这个题是一个比较简单的排列组合的题。。。

其实就相当于是多重集合的排列而已嘛

我们把这个题转化一下：

不同的盒子，不同的球，盒子必须放满

那其实就相当于是：

盒子必须放满的话我们可以新创建一个盒子，用来放下剩下的没有盒子要的球，然后求一遍排列

那么我们考虑这么一件事情

对于两个1-n的排列来说，他们两个等价说明什么，说明在至少一个盒子里面，他们的球一样但是顺序不对

那我们就可以转化成多重集合的排列，一样的盒子里面的球变成一样的，只要有一个球到了其他的盒子里面而不是原来的盒子里面就说明是一种新的情况

但是这个题很恶心(好歹是个紫题)

他告诉我们说的是：模数不一定为质数（真讨厌，国家集训队还出这种题

我们借鉴一下扩展lucas的思想

把上下的阶乘都化简一下，求出逆元就可以了

上面说的不考仅仅是指的NOI系列比赛

P3223 排队

题目链接

这个题大水题好吧

高 精 度 啊 对 不 起 打 扰 了

我 没 写 所 以 就 不 放 代 码 了 。 。 。

这道题还是比较水的吧，一眼题

我们把男同学和老师看做板子，用插板法

我们先把两个老师随便的情况算出来，然后算出强制让两个老师站在一起的方案数

两者相减就是答案

BZOJ 2467 生成树

题目链接

这个题还是比较简单的（我在课上切了没和ZRQ说做法

（我不会证明

我们可以手膜一遍发现一个小结论：在几个五边形都各自随便断掉一条边的情况下,会出现正好一个环（然后随便断一条边就可以了……

所以说我们就相当于一个五边形断掉两条边，其他的断掉一条边就可以了

完了……

BZOJ 3782 上学路线

题目链接

这个题还是比较妙的一个题

首先我们考虑：

对于一个点(x,y)来说，到他的方案数是不是就是不经过它左下角任意一个点的方案数

那么我们就可以用容斥

考虑如果经过左下角的点的话：

我们枚举第一个经过的点，钦定这个点一定会被经过，这个点的左下角的点一定不被经过，

由于是枚举进行求解，我们是知道从源点到左下角的方案数的（不经过任何障碍

从这个点走道我们当前计算的点的时候就直接组合数进行计算（求解方案数的时候直接组合数求向上走的方案数

然后就算完了

（请注意模数哦，要用CRT进行求解的

P3166 数三角形

题目链接

这个题挺好的，就是难度有一点点的虚高。。。（最多是个蓝的绝对到不了紫

显然我们就可以想到容斥

我们只要求出来三点共线的方案数就可以了

首先：三点共线是分不同的情况的：横着，竖着，斜着

那横竖都好求，就是斜着的时候不太好求

我们手膜一下，我们会发现，一个点到一个距离它为(x,y)的点上连线的时候，这条线段上的格点数量应该是gcd(x,y)+1

那么我们枚举一下线段，只是枚举从原点开始的点，求出来方案数

那么我们还可以发现，我们求不了其他点为原点时候的方案（线段的方案数在下面

真的吗？

显然假的

我们可以把这个线段进行一下平移，平移之后就可以出现其他的了（并且我们只考虑斜率为正的线段，最后需要乘上2

那么这条线段能平移出来几条线段呢？显然是(n-x)*(m-y)条把

那么还有一个问题：

这个线段上的可选的点会不会重复选呢？

好解决：我们枚举线段的时候，将两端的点设为必选，那么三点共线的方案数就是gcd(x,y)-1了，不需要考虑起点终点因为有平移的话不需要考虑

然后就做完了（这个题好歹没有CRT这种坑货的东西

P2606 排列计数

题目链接

这个题我感觉其实和上面数三角形差不多…(但是这个题的评级还可以)

这个题其实就相当于是让我们求一遍小根堆的个数。。。(手膜转化一下)

那我们其实只要dp一下就可以了

设f[i]为以i为根的小根堆的方案数

那么f[i]是可以通过来求出左右子树来进行方案数的排列的

$$f[i]=f[ i << 1 ] * f[ (i<<1) | 1 ] * { siz[i] - 1 \choose siz[ i<<1 ] }$$

就是把左右两边的数进行了一下排列而已，选择一下左子树选那几个数字（只要确定了选哪几个数字方案数就确定了