组合数学总结
序言:这东西是我很早就知道的,但一直不是很清楚,于是就借一次做题再次复习了一下,大佬轻喷。
基础
排列
排列的定义
从(n)个不同元素中,任取(m)((m≤n),(m)与(n)均为自然数,下同)个元素按照一定的顺序排成一列,叫做从(n)个不同元素中取出(m)个元素的一个排列;从(n)个不同元素中取出(m)((m≤n))个元素的所有排列的个数,叫做从(n)个不同元素中取出(m)个元素的排列数,用符号(A(n,m))表示,写作(A^m_n)。
计算公式:$A^m_n=frac{n!}{(n-m)!} $
组合
组合的定义
从(n)个不同元素中,任取(m)((m≤n))个元素并成一组,叫做从(n)个不同元素中取出(m)个元素的一个组合;从(n)个不同元素中取出(m(m≤n))个元素的所有组合的个数,叫做从(n)个不同元素中取出(m)个元素的组合数。用符号(C(n,m))表示。
计算公式:$C^m_n=frac{n!}{m!(n-m)!} $
TIP:
代码建议预处理阶乘
拓展1
全错位排列(装错信封问题)
错排的定义
(n)个有序的元素应有(n!)个不同的排列,如若一个排列使得所有的元素不在原来的位置上,则称这个排列为错排。
计算公式:$D_n=n!(frac{1}{2!}-frac{1}{3!}+...pmfrac{1}{n!}) $
注意:一般不直接暴力算(D_n),利用(D_n=(n-1)(D_{n-1}+D_{n-2}))递推式线性预处理。
拓展2
卢卡斯定理
内容
Lucas定理是用于处理组合数取模的定理
通常用于解决阶乘无法解决的问题。
(Lucas(n,m,p)=C(n\%p,m\%p) imes Lucas(frac{n}{p},frac{m}{p},p))
其中 (Lucas(x,0,p)=1),(C(a,b)=(frac{a!}{(a-b)!})^{(p-2)} mod p)
实现代码
inline ll c(int x,int y){
if(y>x) return 0;
return (a[x]*qpow(a[y],p-2)%p*qpow(a[x-y],p-2)%p);
}
inline ll lucas(int a,int b){
if(b==0) return 1;
else return c(a%p,b%p)*lucas(a/p,b/p)%p;
}//a数组是线性预处理的
例题
P4071 [SDOI2016]排列计数
题目描述
求有多少种(1-n)的排列(a),满足序列恰好有(m)个位置(i),使得(a_i = i)。
答案对(10^9 + 7)取模。
输入格式
本题单测试点内有多组数据。
输入的第一行是一个整数 (T),代表测试数据的整数。
以下(T)行,每行描述一组测试数据。
对于每组测试数据,每行输入两个整数,依次代表(n)和(m)。
输出格式
共输出 (T) 行,对于每组测试数据,输出一行一个整数代表答案。
输入输出样例
输入
5
1 0
1 1
5 2
100 50
10000 5000
输出
0
1
20
578028887
60695423
(1 leq T leq 5 imes 10^5,1 leq n, m leq 10^6)。
题解
此题很好分析,公式如下:(ans=C^m_n*D_{n-m}),但是数据很大,在算组合数的时候要%运算,则需要用到lucas定理。
代码
#include <bits/stdc++.h>
using namespace std;
inline ll qpow(ll a,ll b){
ll x=1,y=a;
while(b>=1){
if(b%2==1) x=x*y%mod;
y=y*y%mod,b/=2;
}
return x;
}
ll qw[1000005],we[1000005];
inline ll c(int x,int y){
return (we[x]*qpow(we[y],mod-2)%mod*qpow(we[x-y],mod-2)%mod);
}
inline ll lucas(int a,int b){
if(b==0) return 1;
else return c(a%mod,b%mod)*lucas(a/mod,b/mod)%mod;
}
int T,a,b;
int main() {
qw[2]=1,we[1]=1;
for(re i=3;i<=1000000;++i)
qw[i]=((i-1)*((qw[i-1]+qw[i-2])%mod))%mod;
for(re i=2;i<=1000000;++i)
we[i]=we[i-1]*i%mod;
read(T);
while(T--){
read(a),read(b);
if(a==b) cout<<1<<endl;
else if(a-b==1) cout<<0<<endl;
else if(b==0) cout<<qw[a]<<endl;
else write((lucas(a,b)%mod*qw[a-b])%mod),puts("");
}
return 0;
}