【数论：组合数学】排列组合

知识点

一 . 加法原理与乘法原理

加法原理：分类思想。一个事件的发生，分为几类事件的发生，通俗的说是好几种情况的发生，通常几类事情之间不会相互影响。

乘法原理：分步思想。一个事件的发生，分为几个子事件分步发生，即每个子事件按顺序发生，子事件是独立的，内部发生的概率一样。
 

---

一 . 加法原理与乘法原理

（一）加法原理

（二）乘法原理

例题：洛谷 P3197 [HNOI2008]越狱

思路：在当前条件下，能导致越狱的情况很多，但是不能越狱的情况，只需保证相邻的两个房间的犯人宗教不同即可。总情况减去不能越狱的情况就是能导致越狱的情况。

 在不考虑能否越狱的情况下，有n个房间，m种宗教，总共有种情况。保证不能越狱的条件下，第一个房间的犯人可以有m种宗教的选择，后面 n-1 个房间的犯人只需保证与前一个房间的宗教不同即可，有 m-1 种情况，总共有  种情况。那么最后得到可能发生越狱的情况总数为  种。最后，在此题中，指数增长会导致循环超时，需要进行快速幂优化。

未优化代码（30分）：

#include 
#include 
#include 
#include 
#define ll long long
#define re register
using namespace std;
const int mod=100003; 
ll int n,m,res1=1; //res1用于统计总情况数
inline ll int read()
{
	ll int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
 
inline void write(ll int x)
{
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
 
int main()
{
	m=read(); n=read();
	for(re ll int i=1;i<=n;++i)
	{
		res1=(res1*m)%mod;	
	}
	ll int ans=m-1,res2=m; //res2用于统计不能越狱的情况
	for(re ll int i=1;i<=n-1;++i)
	{
		res2=(res2*ans)%mod;
	}
	write(res1-res2);
	return 0;
}

优化代码：（使用快速幂进行优化）

#include 
#include 
#include 
#include 
#define ll long long
#define re register
using namespace std;
const int mod=100003; 
ll int n,m,res1=1,res3;
inline ll int read()
{
	ll int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
 
inline void write(ll int x)
{
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
 
inline ll int poww(ll int x,ll int y)
{
	ll int ans=1;
	if(y==0) ans=1;
	while(y>0)
	{
		if(y & 1)
		{
			ans=(ans*x)%mod;
		}
		x=x*x%mod;
		y=y>>1;
	}
	return ans%mod;
}
 
int main()
{
	m=read(); n=read();
	res1=poww(m,n)%mod;	
	ll int ans=m-1,res2=m;
	res2=res2*poww(m-1,n-1)%mod;
	res3=res1-res2;
	if(res3<0) res3+=mod; 
        //可能会出现总情况数取模后的数小于不能越狱情况下取模后的数，结果会为负数
	write(res3);
	return 0;
}

二 . 组合数的应用

1 . 组合数与杨辉三角

例题： 洛谷 P2822 [NOIP2016 提高组] 组合数问题

 （待填坑）

#include 
#include 
#include 
#include 
#define ll long long
#define re register
using namespace std;
ll int t,k,m,n;
const int maxn=2e3+5;
ll int c[maxn][maxn],sum[maxn][maxn];
inline ll int read()
{
	ll int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
} 
 
int main()
{
	t=read(); k=read();
	c[0][0]=c[1][1]=1; //在进行查找前进行数据存储
	for(re ll int i=1;i<=2000;++i)
	{
		c[i][0]=1;
		for(re ll int j=1;j<=2000;++j)
		{
			c[i][j]=(c[i-1][j]%k+c[i-1][j-1]%k)%k;
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
			if(c[i][j]==0 && i>=j)
			{
				sum[i][j]++;
			}
		}
			sum[i][i+1]=sum[i][i];
		}
	
	while(t--)
	{
		n=read(); m=read();
		if(m>n) printf("%lld\n",sum[n][n]);
		else printf("%lld\n",sum[n][m]);
	}
	return 0;
}

2 . 计算平面图形的对角线

例题： 洛谷 P2181 对角线

题目描述

对于一个 n 个顶点的凸多边形，它的任何三条对角线都不会交于一点。请求出图形中对角线交点的个数。

例如，6 边形：

输入格式

输入只有一行一个整数 n，代表边数。

输出格式

输出一行一个整数代表答案。

输入输出样例

输入 #1

3

输出 #1

0

输入 #2

6

输出 #2

15

说明/提示

数据规模与约定

• 对于 50% 的数据，保证 。
• 对于 100% 的数据，保证 。

 思路：

对于一个多边形来说，任意选不同的四个点就可以产生一个由于对角线相交而产生的交点，也可以看做是一个四边形的两条对角线交于一点，求四边形的数量。因此可以得到式子：（注：4!=4*3*2*1）。需要注意的是：数据范围特别大，可能会超过long long，这里采用unsigned long long。

#include 
#include 
#include 
#include 
#define ll unsigned long long
using namespace std;
ll int n;
inline ll int read()
{
	ll int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
 
inline void write(ll int x)
{
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
 
int main()
{
	n=read();
	ll int res=n*(n-1)/2*(n-2)/3*(n-3)/4; 
        //几个数相乘以后就除以几，可以保证数据不会增长得太大导致结果错误
	write(res);
	return 0;
}