Day8:组合数学

Luogu 2018 SummerCamp

加法原理与乘法原理：

加法原理

如果为了达成目标有$n$种方法，每种方法有$a_i$种子方法，那么总共有$\Sigma^n_{i=1}a_i$

乘法原理

如果为了达成目标有$n$步，每步有$a_i$种实现方法，那么总共有$\Pi^n_{i=1}a_i$种

栗子：路线条数问题

一个有向图从起点走到终点到底有多少条路径？

可以用拓扑排序等方法解决。

排列与组合

排列

将$n$个人排成一排有多少种排法？

可以应用乘法原理，得出共有$n!$种方法

把$n$个人取$m$个人，排成一排，共有多少种方法？

也应用乘法原理，得出有$n*(n-1)*(n-2)*...*(n-m+1)$种。

这类 排列 问题可以被总结为$A^m_n = {{n!} \over {(n-m)!}}$

组合

组合数：从$n$个元素中不考虑顺序地取$m$个。

因为不考虑顺序，所以只需要在排列数的基础上除以全排列就好了

$C^m_n = {{n!} \over {m!(n-m)!}}$

组合数也可以用dp方法求。

$C^m_n = {C^m_{n-1} + C^{m-1}_{n-1}}$ //杨辉三角 Pascal公式

时间复杂度是$O(n^2)$

常用方法

捆绑法

可以用的栗子

$8$个人排成一排，其中有$2$个人必须站在一起，有多少种方案？

两个人可以作为一个捆绑起来的元素，用$7$个人进行排列，然后$2$个人的顺序可以调换，所以最后的数量为

$$A^2_2 A^7_7$$

不能用的栗子

$8$个人选$4$个人，有$2$个人必须一起选或一起不选，有多少种方案？

不能用捆绑法，因为捆绑后其他的都是$1$个人，而捆绑的是$2$个人，所以只能分类讨论：$$

隔板法

有$8$个人，但是有$2$个人不能站在一起，那么有多少种方法？

先把$6$个人排在一起，然后在$7$个空位种插入$2$个，方案数为

$$A^6_6 A^2_7$$

集合${1,2,...,n}$取$r$个元素，不相邻，求方案数

用隔板法，$n-r$个点，插$r$隔板，那么插板后编号就是一种方案。

预处理求组合数

$C^m_n = {{n!} \over {m!(m-n)!}}$

我们消去$(m-n)!$，除法可以直接用求逆元的方法求。

预处理出阶乘数组a[]和逆元前缀积数组b[]，那么

$$C^m_n \mod p = a_nb_mb_{n-m} \mod p$$

阶乘数组容易计算出，逆元数组可以用费马小定理求出$O(n\log n)$，但是也可以线性递推：($p$是质数模数)

inv[1] = 1; //取模的p一定要是质数
for(int i=2; i<p; i++)
    inv[i] = (p-p/i)*inv[p%i]%p;

这样复杂度是$O(n)$的，可以背下来，证明可以在网上找，然后就可以$O(n)$预处理，$O(1)$求组合数。
由于逆元$inv$是积性的，我们可以先求出$inv(n!)$，然后递推：

b[n] = Inv(n); //可以用快速幂或exgcd
for(int i=n-1; i>=1; i--)
    b[i] = (b[i-1] * (i+1)) % p; //这种方法比之前的好记
for(int i=n; i>=1; i--)
    inv[i] = b[i] * a[i-1]; //a[i] = i!

费马小定理求逆元要求模数必须是质数
$exgcd$求逆元只要两个数互质就可以了

二项式定理

$(x+a)^n$的展开式是：
把$x$降幂排列，$a$升幂排列
第$i$项添上系数$C^{i-1}_n$

可以把$n$个(x+a)展开，利用组合数理解。

栗子：

求$C^1_{10}+C^2_{10}+C^3_{10}+...+C^{10}_{10}$

可以设$f(n)=(x+2)^n$，代入$x=1$即可

栗子：

证明：组合数中$C^i_n$中$i$为奇数的和等于$i$为偶数的和

用二项式定理，代入$(1+(-1))^n$即可。

栗子：P3414 组合数

直接套用二项式定理，输出$2^{n-1} \mod 6662333$即可。

二项式定理有各种形式和扩展，可以自行查阅。

杨辉三角

求杨辉三角中某一列一部分的和。

我们可以注意到，第$n$列是第$n-1$列的前缀和，然后我们只需要加上一个额外的元素，就可以直接利用一个元素算出前面的所有的和。

栗子：NOIP2016提高组 D2T1

组合数取模

给定$p,i$，求$C^i_p \mod p$，满足$p$为质数，$i,p <= 10^9$

只要$i$不为$0$或$p$，那么答案一定是$0$。

$p$是质数，其他情况分子不可能约掉$p$

printf("%d\n", i==0||i==n?1:0);

Lucas定理

当$p$为质数时：

$$C^m_n \equiv C^{\lfloor {m \over p} \rfloor}_{\lfloor {n \over p} \rfloor}C^{m \mod p}_{n \mod p}\quad(\mod n)$$

int lucas(int n, int m, int p){ //p是质数
    if(m > n) return 0;
    if(n<=p && m<=p) return C(n, m);
    else return lucas(n/p, m/p) * lucas(n%p, m%p);
}

可以将$n$转成$p$进制，$m$转成$p$进制，然后把每一位作组合数，最后乘起来，可以方便理解。