排列组合
排列组合顾名思义，就是解决一些排列和组合方法的问题。
加法与乘法原理
加法原理
定义:做一件事情，完成它有$N$类方式，第一类方式有$M_1$种方法，第二类方式有$M_2$种方法，……，第$N$类方式有$M_N$种方法，那么完成这件事情共有$M_1+M_2+……+M_N$种方法。
举个例子：比如AC第一题有三种算法，第二题有二种算法，第三题有四种算法，那么只AC一道题就有$2+3+4=9$种方法。
乘法原理
定义:做一件事，完成它需要分成$N$个步骤，做第一 步有$M_1$种不同的方法，做第二步有$M_2$种不同的方法，……，做第$N$步有$M×N$种不同的方法。那么完成这件事共有$M_1×M_2×……×M_N$种不同的方法。
比较经典的例子：算数基本定理
算数基本定理：如果有一个数$x$，他的质因数分解为
$$x=p_1^{t_1}p_2^{t_2}…p_k^{t_k}$$
那么它的因子就有
$$(t_1+1)(t_2+1)(t_3+1)…(t_k+1)个$$
证明：这里就用到了乘法原理了。
显然对于这个数的每个质因子都可以选$[0,t_i]$个，所以有$t_i+1$种选择，所以根据乘法原理，就可以得到因子个数。
例题
大水题，$n*n$的棋盘上摆放$n$个互不攻击的车，有多少种方法。
根据乘法原理，第一行放置有$n$个格子可以选择，但是放置之后，第二行就只有$n-1$个格子了，所以依次下去，答案就是$n!$
code
Pólya定理
先挖个坑 回头慢慢填 前面的太长了(群论基础到转置到polya 好多)
就先从例题说一下吧
例题
SGU 282 同构
题目描述
我们把使得每对顶点都被恰好一条边连接，且被M种不同颜色之一染色的无向图叫做染色图。如果可以把某张染色图的顶点重新编号使得它和另一张染色图完全相同（即每条对应边的颜色都相同），我们就说这两张染色图是同构的。
给你$N,M$和素数$P$。你需要找到有N个顶点的两两互不同构的染色图数量。输出这个数模P的值。
输入格式
输入一行三个整数$N,M,P(1<=N<=53,1<=M<=1000,P$是素数且$P<=10^6)$。
输出格式
输出一行一个正整数，即互不同构的染色图数量模P的值。
样例输入
sample 1:
1 1 2
sample 2:
3 2 97
sample 3:
3 4 97
样例输出
sample 1:
1
sample 2:
4
sample 3:
20
题解
$n$个点的图有$n!$个置换，枚举肯定不可能的所以可以把$n$分解成若干个环，那么剩下的多于计算的就可以省去了那么不同环上的$a，b$两点，显然轮换个数为$gcd(n_a,n_b)$然后套polya即可
#uncomplete
code
using namespace std;
typedef long long ll;
ll num[maxn],cnt[maxn],res,factor[maxn],n,m,p,ans;
void init()
{
ans=res=0;
factor[0]=1;
for(int i=1;i<maxn;i++)
factor[i]=factor[i-1]*i%p;
}
ll gcd(ll a,ll b)
{
if(a<b)return gcd(b,a);
if(b==0)return a;
return gcd(b,a%b);
}
ll mod_pow(ll a,ll b,ll p)
{
ll ans=1ll;
a%=p;
while(b)
{
if(b&1) ans=(ans*a)%p;
a=(a*a)%p;
b>>=1;
}
return ans;
}
void dfs(ll now,ll left)
{
if(left==0)
{
ll a=1,b=0;
for(ll i=0;i<res;i++)
{
a=a*mod_pow(num[i],cnt[i],p)%p*factor[cnt[i]]%p;
b+=cnt[i]*(cnt[i]-1)/2*num[i]+num[i]/2*cnt[i];
for(ll j=i+1;j<res;j++)
b+=cnt[i]*cnt[j]*gcd(num[i],num[j]);
}
a=mod_pow(a,p-2,p)*factor[n]%p;
ans=(ans+a*mod_pow(m,b,p)%p)%p;
}
if(now>left)return ;
dfs(now+1,left);
for(ll i=1;i*now<=left;i++)
{
num[res]=now,cnt[res++]=i;
dfs(now+1,left-i*now);
res--;
}
}
int main()
{
while(~scanf("%lld%lld%lld",&n,&m,&p))
{
init();
dfs(1,n);
ans=ans*mod_pow(factor[n],p-2,p)%p;
printf("%lld\n",ans);
}
return 0;
}
组合数
这是一个基于乘法原理的东西。
首先看看什么是
排列
定义：从$n$个不同的元素中，有次序的选取$r$个元素，记为$n$中取$r$个的排列，数量记为$A(n,r)$,当$n=r$时，叫做全排列
$$A(n,r)=\frac {n!} {(n-r)!}$$
而且$A(n,r)通常表示为A^n_r$
组合数
定义：组合数，从$n$个不同的元素中选取$r$个切不考虑顺序，记作$C(n,r)$或$C_r^n$
$C^n_m=\frac {p(n,r)} {r!}=\frac {n!} {m!(n-m)!}$
事实组合数和排列经常一起运算来计算一些东西。
常见性质
这些东西可以用组合论证来解释，即将其表示为长度一定的二进制串中某一位选0或者选1
1.$C^n_m=C^n_{n-m}$
这个应该很好想，从$n$中取$m$个为1跟找$n-m$个为0是一样的。
2.$C^n_m=C^{n-1}_{m-1}+C^{n-1}_m$
长度为$n$的串有$m$个1，可以是长度为$n-1$有$m-1$个1的加一个1，或者是$n-1$有$m$个1的加一个0
3.$2^n=\sum_k C^n_k$
长度为$n$的串根据乘法原理有$2^n$个，根据加法原理有分别有$1…n$个1的串加起来那么多个
4.$(a+b)^n=\sum_{k=0}^nC^n_k a^kb^{n-k}$
著名的二项式定理，其还有推广过的多项式定理。
说实话这个用组合论证很麻烦。
这就是$(a+b)^n$的展开形式的解释：首先看后面的多项式，就是从$n$个$a$里面选了$k$个，剩下$n-k$个$b$，其可能数就是前面的系数。
5.$C^{n+m}_r=\sum_kC^n_kC^m_{r-k}$
在$n+m$长度中选$r(r<n,r<m)$个1，那么就是在$n$个中选$k$个和在$m$个中选$r-k$个。
组合数的计算就可以避免时间复杂度低的阶乘，可以通过2来实现。
Catalan
令$h(0)=1,h(1)=1$，catalan数满足递推式:
$h(n)= h(0)×h(n-1)+h(1)×h(n-2) + … + h(n-1)×h(0) (n>=2)$
卡特兰数应用有很多三角形划分等等等
把前几个打出来，回头打表找规律吧
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012,
Stirling
斯特林数有两类
第一类
递推
第二类
递推
边界条件都是$S(p,p)=1 ,p>=0 \ S(p,0)=0 ,p>=1$
应用未完待续
容斥原理
定义
baidu：在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理
画个vinn图很清晰明了啊
加一个口诀吧：单加双减
挺简单的对吧
数学公式很不友好
抽屉原理
好久之前做过一道跟抽屉原理有关的题啊，忘掉了。
是一套模拟题里面的，可以优化复杂度。
抽屉原理就是比如二种苹果放到五个抽屉中，总有一个抽屉出现重复种类的苹果。
再比如去掉大小王的扑克牌，抽14张，总有两张点数相同的。