模板 - 数学 - 组合数学

佚名 5年前 (2019-04-13) 随笔 700人围观抢沙发百度已收录

该模板已经废弃，请移步新模板！

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

1.隔板法

　　用于解决在两个球之间可以多次插入的问题：

　　当要求两个隔板间不必要有球时，那么就隔板和球加起来做一次全排列，假如隔板无差别就要除以隔板的排列，假如球无差别就要除以球的排列。

　　当要求两个隔板间一定要有球的时候，假如有 $k$ 个隔板，那么分成 $k+1$ 组，加入 $k+1$ 个球，变成 $n+k+1$ ，在球之间的 $n+k$ 个空挡中选 $C_{n+k}^k$ 个位置排列入隔板，假如隔板无差别就要除以隔板的排列。

2.d维物体切n刀

　　$\sum\limits_{i=0}^{d}C_n^i$

去你的，模板一堆bug，比我还菜就不要分享出来了好不好。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll n,m,p=20100403;
ll inv[2000000+5];
ll fac[2000000+5];
ll invfac[2000000+5];

//快速幂 x^n%p
ll qpow(ll x,ll n) {
    ll res=1;
    while(n) {
        if(n&1)
            res=res*x%p;
        x=x*x%p;
        n>>=1;
    }
    return res%p;
    //要记得模p，否则输入一个2的幂次模1就挂了
}

//快速乘 a*b%p 防止乘法溢出ll
ll qmut(ll a,ll b) {
    ll res=0;
    while(b) {
        if(b&1)
            res=(res+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return res;
}

//乘法逆元 快速幂+费马小定理 模必须是质数
ll inv_p(ll n) {
    return qpow(n,p-2);
}

//扩展欧几里得算法：返回 g=gcd(a,b) ，以及对应的等式 ax+by=g 的解
ll exgcd(ll a,ll b,ll &x,ll &y) {
    if(!a&&!b)
        return -1;
    if(!b) {
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

//扩展欧几里得算法求逆元，只要求 a,m 互质
ll inv_rp(ll a,ll m) {
    ll x,y;
    ll d=exgcd(a,m,x,y);
    if(d==1)
        return (x%m+m)%m;
    return -1;
}

//线性求乘法逆元
void init_inv(int n) {
    _inv[1]=1;
    for(int i=2; i<=n; i++) {
        _inv[i]=_inv[p%i]*(p-p/i)%p;
        //cout<<"inv["<<i<<"]="<<_inv[i]<<endl;
    }
}

//线性求阶乘、阶乘乘法逆元
void init_fac_invfac(int n) {
    init_inv(n);
    fac[0]=1,invfac[0]=1;
    for(int i=1; i<=n; i++) {
        fac[i]=fac[i-1]*i%p;
        invfac[i]=invfac[i-1]*_inv[i]%p;
    }
}

//利用阶乘和阶乘逆元计算排列数A_n^m
ll A(ll n,ll m) {
    return fac[n]*invfac[n-m]%p;
}

//直接计算排列数A_n^m
/*ll A(ll n,ll m){
    if(m>n) return 0;
    ll u=1;
    for(int i=n-m+1;i<=n;i++)
        u=u*i%p;
    return u;
}*/

//利用阶乘和阶乘逆元计算组合数C_n^m
ll C(ll n,ll m) {
    //ll ans=fac[n]*invfac[n-m]%p*invfac[m]%p;
    //cout<<ans<<endl;
    return fac[n]*invfac[n-m]%p*invfac[m]%p;
}

//直接计算组合数C_n^m
/*ll C(ll n,ll m){
    if(m>n) return 0;
    ll u=1,d=1;
    for(int i=n-m+1;i<=n;i++)
        u=u*i%p;
    for(int i=1;i<=m;i++)
        d=d*i%p;
    return u*inv(d)%p;
}*/

//卢卡斯定理计算组合数C_n^m%p，p是质数
ll lucas(ll n,ll m) {
    if(m>n)
        return 0;
    ll ans=1;
    for(; m; n/=p,m/=p)
        ans=ans*C(n%p,m%p)%p;
    return ans;
}