组合数学




因为组合数学涉及面广,采取边学边更新.

预计大部分会摘自《组合数学》

【鸽巢定理】

也叫作狄利克雷抽屉原理以及鞋盒原理.
对于鸽巢定理的简单阐释,粗略的说就是如果有许多鸽子飞进不够多的鸽巢内。那么至少要有一个鸽巢被两个或多个鸽子占据.

简单形式

很通俗的定理 : 如果要把n+1个物体放进n个盒子内,那么至少有一个盒子包含两个或更多的物体.

简单应用

  1. 在13个人中存在两个人,他们的生日在同一个月份里.

  2. 设有n对已婚夫妻,至少从这2n个人中选出n+1个人可以保证有一对夫妻.

应用3

这一条要拿出来,因为比较重要

证明

考虑m个和:
a_1,a_1+a_2,a_1+a_2+a_3,…,a_1+a_2+a_3+…+a_m
如果这些和当中的任意一个可被m整除,那么结论就成立。因此,我们可以假设这些和中的每一个除以m都有一个非零余数,余数等于1,2,3,4,…,m-1中的一个数。因为有m个和,而只有m-1个余数,所以必然有两个序列的和除以m有相同的余数.因此,存在整数$$k,l,k \< l$$,使得$$a_1+a_2+...+a_k$$和$$a_1+a_2+...+a_l$$除以$$m$$有相同的余数$$r$$: $$a_1+a_2+...+a_k = bm+r,a_1+a_2+...+a_l = cm+r$$ 二式相减,我们发现$$ a_{k+1} $$+$$a_{k+2}+...+a_l = (c-b)m$$。 从而推断出,$$m$$个正整数的序列.一定存在一组序列的和为$$m$$的整数倍. 上面的Latex公示如果没显示完全看下面的图片(PS:Latex公式好麻烦,而且支持也好麻烦):

具体应用POJ2356

题意:输入N个正整数,选择序列中的一些数字,使其和为N\*k(k为正整数).
代码:

//问从N个数中选取多少个数,使得这些数的和%N==0
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=10000+10;
int num[maxn],sum[maxn];
int r[maxn];
int main(){
    int N,ans=0,k=0,l=1;
    memset(r,-1,sizeof(r));
    scanf("%d",&N);
    sum[0]=0;

    for(int i=1;i<=N;++i){
        scanf("%d",&num[i]);
        sum[i]=sum[i-1]+num[i];

        int remainder=sum[i]%N;
        if(remainder==0){
            ans=i;
            k=0;
            l=i;
        }else if(r[remainder]!=-1){
            ans=i-r[remainder];
            k=r[remainder];
            l=i;
        }else r[remainder]=i;
    }
    printf("%d\n",ans);
    for(int i=k+1;i<=l;++i){
        printf("%d\n",num[i]);
    }
    return 0;
}

基本计数方法

加法原理

做一件事情有n种方法,第i中方法有Pi种方案,则一共有P1+P2+P3+…+Pn种方法.

乘法原理

做一件事情有n个步骤,第i个步骤有Pi种方案,则一共有P1P2P3…Pn中方案.

容斥原理

最基本的公式:

|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|

常见问题

错位排列

待填充

组合问题

有n个不同的数,选出k个(顺序无关),每个数最多选一次,有多少种选法?

记答案为C(n,k)。把n选k的排列问题看成两个步骤,首先选出k个数的组合,然后把这k个数进行全排列.由乘法原理知:

P(n,k)=C(n,k)*P(k,k)

C(n,k)=n!/((n-k)!k!)

性质1

C(n,0)=C(n,n)=1

性质2

C(n,k)=C(n,n-k)

性质3

C(n,k)+C(n,k+1)=C(n+1,k+1)
通常用于预处理C(n+1,…)

性质4

C(n,k+1)=C(n,k)*(n-k)/(k+1)
使用这个公式可以在O(n)的时间内求出C(n)
但注意不要发生乘法溢出.及后面的除法溢出

性质4通常运用 => 二项式展开

问题:

求(a+b)^n展开式的各项系数

二项式定理

(a+b)^n=Sigma(k=0~n)C(n,k)a^(n-k)b^k

其余三个问题

有重复元素的全排列

有重复元素的全排列

有k个元素,其中第i个元素有Ni个,求全排列个数.

直接看结论,可以简单证得
N1!*N2!*N3!*…*Nn!*ans=N! (移项即可)

可重复选择的组合

可重复选择的组合

有n个不同的元素,每个元素可以选择多次,一共选k个元素,有多少种选法?

例如n=3,k=2有6种

(1,1)、(1,2)、(1,3)、(2,2)、(2,3)、(3,3)

分析:

设第i个元素选xi个,问题转化为求方程x1+x2+…+x3=k的非负整数解的个数.

令yi=xi+1,则答案为
y1+y2+y3+…+yn=k+n

没太搞懂,直接放答案吧

C(k+n-1,n-1)
=C(n+k-1,k)(性质2)

单色三角形

给定空间内的n(n<=1000)个点,其中没有三点共线,每两个点之间都用红色或黑色线段链接.求三条边同色的三角形个数.

考虑非单色三角形.
如果第i个点连接了ai条红边和n-1-ai条黑边,则这些边属于ai(n-1-ai)个非单色三角形。每个非单色三角形被考虑了两次,所以最终答案除以2

1/2*Sigma(i=1~n) ai(n-1-ai)
用总三角形减去非单色即为单色三角形个数

生成函数

母函数是用于解决组合问题计数的一种方法。
在了解它之前我们先看看熟悉的杨辉三角。

杨辉三角的第n行(注意是从0开始标号的)的数字就是(1+x)^n的展开式从低项到高项的各项系数,也可以表示为组合数的形式C(i,n)。如果将两者联系起来我们会发现,(1+x)可以看成对于一件取舍,1=x^0就是不取,x就是取。这样在(1+x)^n的展开式中x^i项的系数就是从n件物品选取i件的方案数。

定义

给定数列a0,a1,a2…an,构造函数

G(x)=a0f0(x)+a1f1(x)+a2f2(x)…anfn(x)

其中G(x)就是该序列的母函数,f0(x),f1(x),f2(x)…fn(x)为标志函数。
母函数主要有两种形式:普通型母函数和指数型母函数。

普通型母函数

先看一个例题:HDU 1085

普通型母函数的标志函数一般为x^0,x^1,x^2…x^n

因为每个硬币有个数限制,但是也不难构造出

G(x)=(1+x+x^2+x^3+…+x^num1)(1+x^2+x^4+…+x^(2∗num2))(1+x^5+x^10+…+x^(5∗num5))

将多项式展开后,x^i项对应的系数就是组成面值为i的方案数。

例题: 51nod 1383

指数型母函数

再看一个例题:HDU 1521

指数型母函数的标志函数一般为x^0/0!,x^1/1!,x^2/2!…x^n/n!,对于x^i/i!表示在一个方案中某个元素出现了i次,而不同位置的该种元素本质不同,所以在记方案数时只算作一种,所以最后结果应处以i!

对于这道题就不难构造出母函数为

G(x)=(1/0!+X/1!+X^2/2!+…+X^a1/a1!)(1/0!+X/1!+X^2/2!+…+X^a2/a2!)(1/0!+X/1!+X^2/2!+…+X^an/an!)

Catalan数列

介绍

待整理

Catalan数列可以解决很多问题.

比如51nod 1120

Catalan前几项

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304, 14544636039226909, 55534064877048198, 212336130412243110, 812944042149730764, 3116285494907301262, 11959798385860453492, 45950804324621742364, ...

应用

一个小链接

Catalan应用及介绍

待整理

三种方法求Catalan整合

注:其中有牵扯Lucas,Lucas在下面,直接放代码,注释在代码中,有对各个类型进行耗时对比

注2:求逆元中牵扯到了费马求逆元和欧拉求逆元

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
const int maxn=1000000+10;
LL h[10100];

//函数功能: 预处理前N向Catalan
//函数参数: n为项数
//适合N比较小的情况
void Catalan(int n){
    h[0] = h[1] = 1;        //h(0)和h(1)
    for(int i = 2; i <= n; i++)    //依次计算h(2),h(3)...h(n)
    {
        h[i] = 0;
        for(int j = 0; j < i; j++) //根据递归式计算 h(i)= h(0)*h(i-1)+h(1)*h(i-2) + ... + h(i-1)h(0)
            h[i] = (h[i]+(h[j] * h[i-1-j])%mod)%mod;
    }
}

///h(n)=C(2n,n)/(n+1) (n=0,1,2,...)
///+逆元+Lucas组合数取模
///预处理逆元的话,大小会被限制,直接求的话可能会有常数
///但是N就可以大一点
///返回第N个catalan数
LL inv[maxn];
void init(){
    inv[1]=1;
    for(int i=2;i<maxn;++i){
        inv[i]=(mod-mod/i)*1ll*inv[mod%i]%mod;
    }
}
///Lucas
LL Power_mod(LL a, LL b, LL p)
{
    LL res = 1;
    while(b!=0)
    {
        if(b&1) res = (res*a)%p;
        a = (a*a)%p;
        b >>= 1;
    }
    return res;
}
LL Comb(LL a,LL b, LL p)
{
    if(a < b) return 0;
    if(a == b) return 1;
    if(b > a-b) b = a-b;
    LL ans = 1, ca = 1, cb = 1;
    for(LL i=0; i<b; ++i)
    {
        ca = (ca*(a-i))%p;
        cb = (cb*(b-i))%p;
    }
    ans = (ca*Power_mod(cb, p-2, p))%p;
    return ans;
}
LL Lucas(int n, int m, int p)
{
    LL ans = 1;
    while(n && m && ans)
    {
        ans = (ans * Comb(n%p, m%p, p))%p;
        n /= p;
        m /= p;
    }
    ///如果等于0则返回1
    return ans==0?1:ans;
}

LL N_L_Catalan(int N){
    return Lucas(2*N,N,mod)*inv[N+1]%mod;
}

///第三种方法
///h(n)=C(2n,n)-C(2n,n+1)
///由上式子可以直接两个Lucas+同余定理解决
///复杂度可能会比第二种方法换成直接求逆元要高点
LL T_Catalan(int N){
    return (Lucas(2*N,N,mod)-Lucas(2*N,N+1,mod)+mod)%mod;
}


///第四种方法
///直接求逆元(扩展欧几里得求逆元)+Lucas
void extgcd(LL a,LL b,LL& d,LL& x,LL& y){
    if(!b){ d=a; x=1; y=0;}
    else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
LL inverse(LL a,LL n){
    LL d,x,y;
    extgcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}

LL F_Catalan(int N){
    return Lucas(2*N,N,mod)*inverse(1ll*N+1,1ll*mod)%mod;
}

///第五种
///欧拉定理求逆元+Lucas
///mod是素数且与N互质
long long Pow(long long a,long long b){
    long long ans=1;
    while(b){
        if(b&1)
        {
            b--;
            ans=(ans*a)%mod;
        }
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}

long long euler(int p)
{
    long long ans=p,a=p;
    long long i;
    for(i=2;i*i<=a;i++)
    {
        if(a%i==0)
        {
            ans=ans/i*(i-1);
            while(a%i==0)
                a/=i;
        }
    }
    if(a>1)
        ans=ans/a*(a-1);
    return ans;
}

long long eu=euler(mod)-1;

long long Einv(long long a)
{
    return Pow(a,eu);
}

LL Fi_Catalan(int N){
    return Lucas(2*N,N,mod)*Einv(1ll*(N+1))%mod;
}

int main(){
    Catalan(10000);
    init();//初始化逆元
    int k;
    while(cin>>k){
        if(k<=10000)
            cout<<"第一种方法(预处理): "<<h[k]<<endl;
        if(k<=1000000)
            cout<<"第二种方法(h(n)=C(2n,n)/(n+1),预处理逆元+Lucas): "<<N_L_Catalan(k)<<endl;
        clock_t startTime,endTime;
        startTime = clock();
        cout<<"第三种方法(h(n)=C(2n,n)-C(2n,n+1),Lucas): "<<T_Catalan(k)<<endl;
        endTime=clock();
        cout<<"  "<<(double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
        startTime = clock();
        cout<<"第四种方法(h(n)=C(2n,n)/(n+1),Lucas+扩欧求逆元): "<<F_Catalan(k)<<endl;
        endTime=clock();
        cout<<"  "<<(double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
        startTime = clock();
        cout<<"第五种方法(h(n)=C(2n,n)/(n+1),Lucas+欧拉定理求逆元): "<<Fi_Catalan(k)<<endl;
        endTime=clock();
        cout<<"  "<<(double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
    }
    return 0;
}

Lucas

介绍

Lucas定理用于对组合数求模

因为组合数是一个大式子,无法直接求模,所以用到了Lucas

Code

///Lucas
LL Power_mod(LL a, LL b, LL p)
{
    LL res = 1;
    while(b!=0)
    {
        if(b&1) res = (res*a)%p;
        a = (a*a)%p;
        b >>= 1;
    }
    return res;
}
LL Comb(LL a,LL b, LL p)
{
    if(a < b) return 0;
    if(a == b) return 1;
    if(b > a-b) b = a-b;
    LL ans = 1, ca = 1, cb = 1;
    for(LL i=0; i<b; ++i)
    {
        ca = (ca*(a-i))%p;
        cb = (cb*(b-i))%p;
    }
    ans = (ca*Power_mod(cb, p-2, p))%p;
    return ans;
}
LL Lucas(int n, int m, int p)
{
    LL ans = 1;
    while(n && m && ans)
    {
        ans = (ans * Comb(n%p, m%p, p))%p;
        n /= p;
        m /= p;
    }
    ///如果等于0则返回1
    return ans==0?1:ans;
}