组合数学总结

序言：这东西是我很早就知道的，但一直不是很清楚，于是就借一次做题再次复习了一下，大佬轻喷。

基础

排列

排列的定义

? 从\(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!}+...\pm\frac{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)\times 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 \times 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;
}