本文主要讲编程比赛中常用的排列组合。
首先，排列组合的公式是（其中P代表的就是A）
最普通的算法就是按照公式求了，即分子算出来，分母算出来，然后相除，写成代码为：
int c( int m,int n ){int a = 1,b = 1, c = 1;for( int i = 1 ; i <= m ; i++ )a = a*i;for( int i = 1 ; i <= n ; i++ )b = b*i;for( int i = 1 ; i <= m-n ; i++ )c = c*i;return a/(b*c);}
很显然，这种方法不好，很容易溢出，只要数据范围一大，就不能行了。
实际上，我们自己在纸上算排列组合的时候也并不是按照公式老老实实的算，其实可以化简，即约分。
比如c（5,4）按照原来的方法=A（5,4）/！4，其实c（5,4）=c（5,1）= 5/1 = 1；
那么就是c（m，n）= m*(m-1)*.......(m-n+1) / ! n 。
写成代码为：
int c( int m,int n ){int a = 1,b = 1;n = min(n,m-n);//求简单一点的 例如C(5,4) 可以求C（5,1）if( n == 0 )return 1;for( int i = m ; i >=m-n+1 ; i-- )a = a*i;for( int i = 1 ; i <= n ; i++ )b = b*i;return a/b;}
这个方法相对于上一个好一点，但是还是有问题，数据太大会溢出，而且不能进行取模运算（反正我不知道）。
那么，再介绍一种方法，递推的思想，
其实排列组合还是挺有规律的，例如下面的
(1,1) (1,2) (1,3) (1,4) (1,5) (1,6)
1 2 3 4 5 6
(2,2) (2,3) (2,4) (2,5) (2,6)
1 3 6 10 15
(3,3) (3,4) (3,5) (3,6)
1 4 10 20
(4,4) (4,5) (4,6)
1 5 15
(5,5) (5,6)
1 6
(6,6)
1
因为具有对称性，我只列了一半，高中书本里介绍过杨辉三角，其实很简单，就是c(n,m)=c(n,m-1)+c(n-1,m-1),对应到上幅图中就是：某一个 等于 这个的左边的 加上 这个左边的上边的。即C(2,3) = C(2,2)+C(1,2)
那么我们先把第一层算出来，然后递推第二层，然后递推。这种方法的优点是一次就把所有的求出来了，而且中间可以进行取模运算。
我们用一个二维数组来存储结果。
代码如下：
int a[1001][1001]; //数组的大小随实际情况而定//数组的类型最好为 long longvoid c( ){memset(a,0,sizeof(a));for( int i = 1 ; i <= 1000 ; i++ )//对第一层初始化 , 范围视情况而定a[1][i] = i,a[0][i] = 1;for( int r = 2 ; r <= 1000 ; r++ )//枚举行for( int c = r ; c <= 1000 ; c++ )//枚举列{a[r][c] = a[r][c-1]+a[r-1][c-1];/*if( a[r][c] > mo )a[r][c] = a[r][c] % mo;取模运算一般题目都会给一个mo，让你取模*/}}
本文只讲了C（m，n）,没有讲A（m,n），实在是能力有限，以后学到相关知识一定补充！
最后给自己打个广告吧，自己做了一个网站，大家可以访问访问
https://www.bowenyang666.com