【常用模板】逆元法快速求模意义下的组合数
浏览 417 | 评论 3 | 字数 1415
TTQ
2020年02月28日
  • 从$n$个不同元素中,任取$m(m \leq n)$个元素并成一组,叫做从$n$个不同元素中取出$m$个元素的一个组合
    从$n$个不同元素中取出$m(m \leq n)$个元素的所有组合的个数,叫做从$n$个不同元素中取出$m$个元素的组合数
    通常我们使用$C(n,m)$来表示组合数。

    重要性质

    $C(n,0)+C(n,1)+C(n,2)+...+C(n,n)=n!$
    其中,我们规定:$C(n,0)=1$ $C(n,n)=1$ $C(0,0)=1$

    思路

    在需要快速求得组合数的情况下,往往是需要求得大小比较大的组合数,此时没有很好的数据存储类型能保存下完整的数据,因此往往需要取模意义下的组合数。
    那么我们就可以使用逆元法来快速求得。(具体证明过程需要用到线性同余方程等知识,内容较多,以后再完善)
    我们需要求$C(m,n)\%p$,$p$为素数(经典$p=10^{9}+7$)。

    虽然我们有公式$C(m,n)=\frac{n!}{m!(n-m)}$

    ,但由于取模的性质对于除法不适用,所以需要把除法转换成乘法,才能借助取模的性质在不爆long long的情况下计算组合数。这时候就需要用到逆元
    首先,我们需要知道什么是逆元:

    逆元:对于$a$和$p$($a$和$p$互素),若$a\times b\%p\equiv 1$,则称$b$为$a\%p$的逆元。

    那这个逆元有什么用呢?试想一下求$(a/b)\%p$,如果你知道$b\%p$的逆元是$c$,那么就可以转变成$(a/b) \% p=a\times c \% p=(a \% p)(c \% p) \% p$
    那怎么求逆元呢?这时候就要引入强大的费马小定理。
    随后,我们需要知道什么是费马小定理:

    费马小定理:对于a和素数p,满足$a^{p-1}\%p\equiv 1$

    接着因为$a^{p-1}=a^{p-2}\times a$,所以有$a^{p-1}=a^{p-2}\times a\%p\equiv 1$!由逆元的定义可得,$a^{p-2}$是$a$的逆元。
    所以问题就转换成求解$a^{p-2}$,也就是变成求快速幂的问题了(当然这需要满足$p$为素数)。

    代码

    ll C(ll n,ll m)
    {
        ll ans = 1;
        for (ll i = 1;i<=m; i++)
        {
            ll tmp;
            tmp = (n - i + 1) % mod;
            ans *= (tmp * qpow(i, mod - 2, mod)) % mod;
            ans %= mod;
        }
        return ans;
    }
    

    接口

    $n$与$m$分别对应组合数$C(n,m)$中的$n$和$m$,$mod$为全局变量,用于取模(需为素数)。

    本文作者:TTQ
    本文链接:https://blog.ponder.fun/archives/30.html
    最后修改时间:2020-07-20 10:38:02
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    与本文无关评论请发留言板。请不要水评论,谢谢。
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    已有 3 条评论
    2020-07-18 15:01
    Nice blog here! Also your web site loads up very fast!
    What host are you using? Can I get your affiliate link to your
    host? I wish my web site loaded up as quickly as yours lol
    2020-06-09 11:08
    Please let me know if you're looking for a article author for your blog.
    You have some really good posts and I feel I would be a goodIf you ever want to take some of the load off, I'd absolutelyto write some material for your blog in exchange for a link backto mine. Please send me an e-mail if interested.
    Thanks! situs sbobet terpercaya
    2020-06-09 10:36
    you're truly a excellent webmaster. The site loading speed is amazing.
    It seems that you are doing any distinctive trick. Furthermore, The contents are masterwork.
    you have performed a wonderful activity on this subject!
    judi online terpercaya indonesia