组合数学总结

seasongirl 2020-04-26

组合数学总结

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

基础

排列

排列的定义

? 从\(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;
}

相关推荐

seasongirl / 0评论 2020-06-05