【全程NOIP计划】组合计数选讲
组合数基础
加法原理
加法原理，总共的等于各个相互独立的相加
乘法原理
两个不相干的事情同时发生，总共的情况是两种情况相乘
抽屉原理
容斥原理
排列数
从n个中选m个，考虑顺序
总的方案数为\(P_n^m=\frac {n!} {(n-m)!}\)，或者可以记录为\(A_n^m\)
P5520 青原樱
思路
实际上就是两个幼苗之间至少有一个空位，然后m个幼苗之间必须有m-1个空位
所以把这m-1个位置空出来，然后剩下的位置乱插
答案就是\(A_{n-m+1}^m\)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int type,n,m,p;
long long A(int n,int m)
{
long long res=1%p;
for(int i=n-m+1;i<=n;i++)
res=(res*i)%p;
return res%p;
}
int main()
{
cin>>type>>n>>m>>p;
cout<<A(n-m+1,m)<<'\n';
return 0;
}
组合数
从n个选m个，不考虑顺序
总的方案数为\(C_n^m=\frac {n!}{m!(n-m)!}\)，实际上选出的人再进行随便的排列组合，一共有\(m!\)种，所以也可以推出来排列数的公式，他们两个之间的关系是\(C_n^m*m!=P_n^m\)
组合数常用的式子
\[C_n^m=C_{n-1}^m+C_{n-1}^{m-1} \]实际上这个就对应杨辉三角形
1
1 1
1 2 1
………………
我们可以知道一个二项式定理
\[(x+y)^n=\sum_{i=1}^n C_n^i*x^iy^{n-i} \]怎么证明？
常见的组合问题
1.20个人去霓虹玩，站成一排拍纪念照，但是anan和他的女朋友必须贴贴，请问有多少种方案
先把他们两个看成一个人
就变成了19个人拍照，站成一排的方案数量为\(19!\)，再排他和他女朋友的方案为2
所以总的方案数量为\(19! \times 2\)
2.20个人去霓虹玩，站成一排拍纪念照，但是anan和他的女朋友吵架了不能贴贴，有多少种方案
实际上可以直接用容斥原理，用总的方案数减去问题1的方案数即可
但是怎么不用容斥原理呢？
先不考虑他们两个人
我们先把剩下18个人排好，方案数量为\(18!\)
然后18个之间，包括最左和最右一共有19个空，再把他和他女朋友放进去，一共有\(P_{19}^2\)的方案数量
所以总的方案数量就为\(18! \times P_{19}^2\)
3.Zcysky大王有n个相同的纸片人老婆，他准备把这些老婆分给m个不同的手下，Zcysky秉持着雨露均沾的原则，每个人至少能分到一个纸片人老婆，一共有多少种方案
使用隔板法，实际上就是在n-1个空里面选m-1个空插，当然，隔板是一样的，所以不用考虑顺序，也就是最后总的方案数为\(C_{n-1}^{m-1}\)
4.Zcysky大王有n个相同的纸片人老婆，他准备把这些老婆分给m个不同的手下，但是他早就看某些人不爽了，所以有些人可能一个人都分不到，一共有多少种方案
还是隔板法，但是有可能两个隔板之间一个纸片人都没有。每个人再发一个老婆，所以一共有n+m-1个空，然后选m-1个插，所以总的方案数量为\(C_{n+m-1}^{m-1}\)
Lucas定理
卡特兰数
\[h(n)=h(0)*h(n-1)+h(1)*h(n-2)+……+h(n-1)*h(0) \\=\sum h(i)*h(n-i-1) \]有什么作用呢？
n对括号匹配的数目
n个节点组成二叉树
n边形三角划分
n个点依次进出栈的出战顺序
n*n的矩阵从左下角到右上角不经过对角线
求卡特兰数有两种方式
\[h(n)=C_{2n}^n-C_{2n}^{n+1} \\h(n)=\frac {C_{2n}^n}{n+1} \]Monochromatic Triangles
题目
空间中有n个点，m条红边，任意3个点不共线
每两个点用红线或者蓝线相连，如果一个三角形的三边颜色相同，那么称为同色三角形
给你一组数据，计算同色三角形的总数
思路
根据容斥原理
同色三角形=三角形总数-不同色三角形数量
则三角形的总数量就为\(C_n^3\)
对于一个点，如果连出去\(d[i]\)条红边，就有\(n-d[i]-1\)条蓝边
根据乘法原理，它贡献的三角形数量就是\(d[i]*(n-d[i]-1)\)
由于一个异色三角形会被计算两遍
答案就是\(C_n^3-\sum \frac{d[i]*(n-d[i]-1)}2\)
P3166 数三角形
题目
给定一个n*m的网络，请计算三点都在格点上的三角形一共有多少个
注意三角形的三点不能共线
思路
任选三个点的方案数减去三点共线的方案数量
任选三个点方案数是\(C_{n*m}^3\)
三点共线的方案数：同一排，同一列，同一斜线
对于同一斜线的可以枚举两个端点，中间的用gcd计算
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
long long n,m;
long long ans;
long long gcd(long long a,long long b)
{
return b? gcd(b,a%b):a;
}
int main()
{
cin>>n>>m;
n++,m++;
ans=(n*m)*(n*m-1)*(n*m-2)/6;//三个点选择的计算公式
if(n>=3)
ans-=(n*(n-1)*(n-2)*m/6);
if(m>=3)
ans-=(m*(m-1)*(m-2)*n/6);
for(int i=1;i<n;i++)
{
for(int j=1;j<m;j++)//枚举斜线，向左斜一遍，向右斜一遍，拒绝早恋
ans-=(n-i)*(m-j)*(gcd(i,j)-1)*2;
}
cout<<ans<<'\n';
return 0;
}
P4478 上学路线
题目
从n*m个网格图的左下角走到右上角
有t个坐标不能经过
只能向上或者向右走
问有多少种不同的走法，对p取模
思路
容斥原理Dp
先把终点当做障碍点，把所有的障碍点按x为第一关键词，y为第二关键字从小到大排序
设\(f[i]\)为到达第i个障碍点且不经过任何障碍点的方案数量
设\(G[i][j]\)表示到达从第i个障碍点到第j个障碍点的方案数量
从（x1,y1）走到(x2,y2)的方案数量为\(C_{x2+y2-x1-y1}^{x2-x1}\)，这个用lucas定理求就可以了
\(f[i]=G[0][i]-\sum G[j][i]*f[j]\)
当p=1000003的时候直接求解
p=1019663265的时候先分解质因数，然后使用CRT合并
矩阵相关
矩阵的定义
有\(m*n\)个数aij排成m行n列的数表称为m行n列的矩阵，简称\(m*n\)矩阵
$ A=\begin{bmatrix} a_{11} & a_{12} &\dots &a_{1n}\ a_{21} & a_{22} &\dots &a_{2n}\a_{31} & a_{32} &\dots &a_{3n}\\dots & \dots & &\dots\a_{m1} & a_{m2} &\dots &a_{mn}\ \end{bmatrix} $
这\(m \times n\)个数组被称为矩阵A的元素
行数与列数都等于n的矩阵称为n阶矩阵或者n阶方阵
矩阵的加减法
加法：\(C=A+B\)，则\(C_{i,j}=A_{i,j}+B_{i,j}\)
\[\begin{bmatrix}1 & 4 & 2 \\ 2 & 0 & 0 \end{bmatrix} + \begin{bmatrix}0 & 0 & 5 \\ 7 & 5 & 0 \end{bmatrix} = \begin{bmatrix} 1+0 & 4+0 & 2+5 \\ 2+7 & 0+5 & 0+0 \end{bmatrix} = \begin{bmatrix} 1 & 4 & 7 \\ 9 & 5 & 0 \end{bmatrix} \]减法:\(C=A-B\),则\(C_{i,j}=A_{i,j}-B_{i,j}\)
\[\begin{bmatrix}1 & 4 & 2 \\ 2 & 0 & 0 \end{bmatrix} - \begin{bmatrix}0 & 0 & 5 \\ 7 & 5 & 0 \end{bmatrix} = \begin{bmatrix} 1-0 & 4-0 & 2-5 \\ 2-7 & 0-5 & 0-0 \end{bmatrix} = \begin{bmatrix} 1 & 4 & -3 \\ -5 & -5 & 0 \end{bmatrix} \]\(C,A,B\)的行数相同，列数也相同
对应位置加减即可，也就是说，如果他们可以加减的话，那么他们的行数相同，列数也相同
矩阵乘法
对应的行数和对应的列数相乘再加起来
\[c_{i,j}=a_{i,1}b_{1,j}+a_{i,2}b_{2,j}+……+a_{i,n}b_{n,j}=\sum_{r=1}^n a_{i,r}b_{r,j} \] \[\begin{bmatrix}1 & 0 & 2 \\ -1 & 3 & 1 \end{bmatrix} \times \begin{bmatrix}3 & 1 \\ 2 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} (1\times 3+ 0 \times 2+2 \times 1) &(1\times 1+ 0 \times 1+2 \times 0)\\ (-1\times 3+3 \times 2+1 \times 1) &(-1\times 1+3\times 1+1 \times 0)\end{bmatrix} = \begin{bmatrix} 5 & 1 \\ 4 & 2 \end{bmatrix} \]矩阵乘法的用途
优化线性递推
一般的，我们只要构造出来一个矩阵，我们可以进行矩阵加速递推
P3216 数学作业
思路
\(f(n)=f(n-1)*10^k+n\)
对于每一段位数相同的n，更改k的值构造矩阵
#include <bits/stdc++.h>
using namespace std;
struct matrix{
long long z[3][3];
} a, b;
long long n,m,temp,pre[20];
matrix operator *(matrix a, matrix b) {
matrix c;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
c.z[i][j]=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
for(int k=0;k<3;k++)
c.z[i][j]=(c.z[i][j]+a.z[i][k]*b.z[k][j])%m;
return c;
}
matrix ksm(matrix x, long long y)
{
if(y==1)
return x;
matrix z=ksm(x,y>>1);
z=z*z;
if(y&1)
z=z*x;
return z;
}
int main()
{
cin>>n>>m;
b.z[0][1]=b.z[0][2]=1;
a.z[1][0]=a.z[1][1]=a.z[2][1]=a.z[2][2]=1;
pre[0]=1;
for(int i=1;i<=18;i++)
pre[i]=pre[i-1]*10;
for(int i=1; ;i++)
{
a.z[0][0]=pre[i]%m;
temp=min(n,pre[i]-1)-pre[i-1]+1;
b=b*ksm(a,temp);
if(pre[i]-1>=n)
break;
}
cout<<b.z[0][0]<<'\n';
return 0;
}
矩阵行列式
定义二阶矩阵行列式
n阶矩阵行列式的和为
\[det(A)=a_{i1}A{i1}+……+a_{in}A_{in}=\sum_{j=1}^na_{ij}(-1)^{i+j}det(A_{ij}) \]行列式的性质
1.矩阵某两行（列）交换，行列式乘以-1
2.矩阵某一行（列），加上另一行列，行列式不变
Min-Max容斥
期望不满足最大最小值的那个玩意儿相乘那玩意儿
那该如何求出\(E(max(X,Y))\)和\(E(min(X,Y))\)的值呢 ？
给定集合S，设max（s）为s中的最大值，min（s）为s中的最小值，则：
\(max(S)=\sum_{T\in S}(-1)^{|T|-1}min(T)\)
\(min(s)=\sum_{T\in S}(-1)^{|T|-1}max(T)\)
Hdu4336
题目
有n种卡片，每一秒都有Pi的概率获得一张第i种卡片，求每张卡片都至少有一张的期望时间
思路
记录max(s)为s中最后获得的那种卡片第一次获得的期望时间
min(s)为s中第一个获得的那种卡片的第一次获得的期望时间
仍然满足上列式子