从$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 授权协议,转载请注明来源,谢谢!
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