OI中组合数的若干求法与CRT

只是下决心整理一下子呢~

一般性的组合数求法

$\binom{m}{n}=\frac{m!}{n!\times (m-n)!}$

一、 $\color{red} \text{杨辉三角法}$

$\binom{m}{n}=\binom{m-1}{n}+\binom{m-1}{n-1}$

复杂度$O(n^2)\sim O(1)$，对$p$无要求

二、 $\color{red} \text{预处理阶乘和阶乘逆元法}$

$\binom{m}{n}=fac_m\times invf_n \times invf_{m-n}$

$invf_{i} \equiv invf_{i+1}\times (i+1) \pmod p$

$fac_i \times invf_i \equiv 1 \pmod p$

$fac_{i-1}\times i \times invf_i \equiv 1 \pmod p$

复杂度$O(n+\log p)\sim O(1)$，$p$为质数

麻烦一些的组合数求法

三、 $\color{red} \tt{Lucas}\text{定理}$

复杂度$O(p+\log p)\sim O(\log n)$,$p$为质数

四、 $\color{red} \tt{lucas}\text{定理}+\tt{CRT}\text{合并}$

两个方法的复杂度是一样的，均为$O(n\log p)$，但实际上普通的$\tt{CRT}$用的更多一些，注意有时候避免乘起来爆$\text{long long}$要用龟速乘

当题目已经给定模数而不是输入模数时，可能会用的到，比如古代猪文这个题。

这个方法的复杂度其实不好具体计算，但跑起来大概像这个$O(\max p_i)\sim O(\log p)$

五、 $\color{red} \tt{exLucas}$

这个的求阶乘复杂度算起来其实是一个等比数列，是$O(n)$的

发现这个东西的复杂度中有一堆并不重要的$\log$，比如$\tt{CRT}$，逆元什么的。真正复杂度瓶颈在于求阶乘的那个$O(n)$，可以近似的认为复杂度是$O(\max p_i^{c_i})$的。

#include <cstdio>
#define ll long long
ll mod;
void exgcd(ll &x,ll &y,ll a,ll b)
{
    if(!b){x=1,y=0;return;}
    exgcd(x,y,b,a%b);
    ll tmp=x;
    x=y;
    y=tmp-a/b*y;
}
ll inv(ll a,ll p)
{
    ll x,y;
    exgcd(x,y,a,p);
    return x;
}
ll quickpow(ll d,ll k,ll p)
{
    ll f=1;
    while(k) {if(k&1)f=f*d%p;d=d*d%p;k>>=1;}
    return f;
}
ll fac(ll n,ll p,ll tp)
{
    if(!n) return 1;
    ll f=1,res=1;
    for(ll i=1;i<tp;i++)
    {
        if(i%p) (f*=i)%=tp;
        if(i==n%tp) res=f;
    }
    f=quickpow(f,n/tp,tp);
    return fac(n/p,p,tp)*f%tp*res%tp;
}
ll C(ll m,ll n,ll p,ll tp)
{
    ll ct=0;
    for(ll i=m;i;i/=p) ct+=i/p;
    for(ll i=n;i;i/=p) ct-=i/p;
    for(ll i=m-n;i;i/=p) ct-=i/p;
    return fac(m,p,tp)*inv(fac(n,p,tp),tp)%tp*inv(fac(m-n,p,tp),tp)%tp*quickpow(p,ct,tp)%tp;
}
ll CRT(ll m,ll n,ll p,ll tp)
{
    return C(m,n,p,tp)*(mod/tp)%mod*inv(mod/tp,tp)%mod;
}
ll exlucas(ll m,ll n,ll p)
{
    ll ans=0;
    for(ll i=2;i*i<=p;i++)
    {
        if(p%i==0)
        {
            ll tp=1;
            while(p%i==0) tp*=i,p/=i;
            (ans+=CRT(m,n,i,tp))%=mod;
        }
    }
    if(p!=1) (ans+=CRT(m,n,p,p))%=mod;
    return (ans%mod+mod)%mod;
}
int main()
{
    ll n,m;
    scanf("%lld%lld%lld",&n,&m,&mod);
    printf("%lld\n",exlucas(n,m,mod));
    return 0;
}

六、 $\color{red} \text{一些灵活一点的应用}$

• 给定一个长为$n(n\le 3\times10^5)$的有重序列，求这个序列在所有排列中的排名，对$p(p\le 2\times 10^9)$取模

• 给出$n(n\le 2\times 10^5)$个质数，求这些质数乘积的约数之积模$10^9+7$

• 有$n(n\le 20)$个集合，第$i$个集合有$c_i(0\le c_i \le 10^{12})$个相同元素，不同集合的元素互不相同，从中取出$m(0\le m\le 10^{14})$个元素，问有多少种取法，对$10^9+7$取膜

PER-Permutation

CF451E Devu and Flowers