首页 > 其他 > 详细

模意义下的组合数

时间:2018-03-05 00:37:39      阅读:248      评论:0      收藏:0      [点我收藏+]

模意义下的组合数

\(C_{n}^{k}\%p\)(p为质数)

\[C_{n}^{k}=\frac{n!}{k!(n-k)!}\]

\(n!=a_1p^{e_1}, k!=a_2p^{e_2}, (n-k)!=a_3p^{e_3}\)
如果\(e_1-(e_2+e_3)>0\),则\(C_{n}^{k}\%p=0\)
否则\(C_{n}^{k}\%p=\frac{a_1}{a_2a_3}\%p=a_1(a_2a_3)^{(p-2)}\%p\)(费马小定理)

LL mod_fact(LL n, LL p, LL &e)
{
    if (n<=1) return 1;
    LL ret=mod_fact(n/p, p, e);
    e+=n/p;
    if ((n/p) & 1) return ret*(fact[n%p]*(p-1)%p)%p;
    else return ret*fact[n%p]%p;
    /* (p-1)!=-1(mod p) */
}
LL calc_C(LL n, LL k, LL p)
{
    LL e1=0, e2=0, e3=0;
    LL a1=mod_fact(n, p, e1);
    LL a2=mod_fact(k, p, e2);
    LL a3=mod_fact(n-k, p, e3);
    if (e1-(e2+e3)>0) return 0;
    return (a1*POW(a2*a3%p, p-2, p)%p);
}

模意义下的组合数

原文:https://www.cnblogs.com/GerynOhenz/p/8506859.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!