组合数取模

求\[{n \choose{m}} \bmod p\]

Subtask 0

杨辉三角...

11 11 2 11 3 3 11 4 6 4 1...

Subtask 1

\[n,m\le 5\times 10^6,n\le p{\color{blue}{\mathtt{:prime}}}\le 10^{18}\]

这个数据范围其实并不良心...因为常数比较大所以...

算法很简单.线性求出阶乘与阶乘的逆元,通过一个大家都知道的转化(pj初赛知识咯...- -)

\[{n\choose m}=\frac{n!}{m!(n-m)!}\]

问题就是如何求阶乘的逆元了咯...

杜教的某课件里写了一种办法,可惜看不懂...但是暴力上也兹瓷哦...

当然要\(O(n)\)求逆元的办法啦...

有个黑科技咯...\(i^{-1}\equiv -\lfloor \frac{p}{i}\rfloor \left( p \bmod i\right)^{-1}\pmod{p}\)

然后只要乘着模着...就没了?

Subtask 2

\[n,m\le 5\times 10^6,n\le p\le 10^{18}\]

如何呢?

\(p\)不是素数,那么就不能逆元求咯...

其实可以先筛出\(n\)以下的所有素数,对于它们统计\(n!\)的此素因数个数...

\[s_d(n)=\sum_i^{\infty}\lfloor \frac{n}{d^i}\rfloor\]

显然只有\(\log_dn\)项...而素数个数是\(O\left(\frac{n}{\log{n}}\right)\)的...所以这部分复杂度线性...

再减一减...再快速幂依然总共线性...

就好了?

Subtask 3

\[n,m\le 10^{18},p{\color{blue}{\mathtt{:prime}}}\le 10^6\]

多组数据...

那么我们考虑预处理出所有\(n! \bmod p\)与它们的逆元...显然对于\(n< p\)的情况可做了...

对于剩下的情况,我们考虑Lucas定理:

\[{n\choose m}\equiv {

{\lfloor\frac{n}{p}\rfloor}\choose{\lfloor\frac{m}{p}\rfloor}}{

{

{n}\bmod{p}} \choose {m\bmod p}}\pmod{p}\]

就可以递归做咯...

一次递归规模缩小为原来\(\frac{1}{p}\),那么询问时间复杂度\(O\left( \log_pn\right)\)

Subtask 4

\[n,m\le 10^{18},p{\color{blue}{\mathtt{:prime}}}^c\le 10^6\]

多组数据...

Lucas定理没法用了...

然而换一个角度想...在\(n!\)中含\(p\)因子的个数是可以算出来的..那么我们可以将所有含\(p\)因子的先剔除,剩下的数应该是按照原来的编号\(p^c\)个相乘在\(\bmod p^c\)下一相等的...

含\(p\)因子的数直接递归处理即可..

发一份没测试过的代码:

#define cmax 25struct Comb_Number_Small2{//O(p^c)    linear_inverse li;    ll facn[maxm],infacn[maxm],pp,cc;    ll pox[cmax];    inline void init(ll p,ll c){        li.mx(n,p);        ll n=1;        pox[0]=n;        foxe(i,1,c) n*=p,pox[i]=n;        facn[1]=1,infacn[1]=1,pp=p,cc=c;        foxe(i,2,n){            facn[i]=facn[i-1],infacn[i]=infacn[i-1];            if(i%p) facn[i]=modmul(facn[i-1],i,p),infacn[i]=modmul(infacn[i-1],li.inv[i],p);        }    }    inline ll facx(ll n){        ll k=n/pox[cc],a=modpow(facn[pox[cc]],k,pox[cc]);        return modmul(a,facn[n%pox[cc]],pox[cc]);    }    inline ll infacx(ll n){        ll k=n/pox[cc],a=modpow(infacn[pox[cc]],k,pox[cc]);        return modmul(a,infacn[n%pox[cc]],pox[cc]);    }    inline ll operator()(ll n,ll m){        if(m>n) return 0;        ll A=n,B=m,C=A-B;        int a=calcp(A,pp),b=calcp(B,pp),c=calcp(C,pp);        ll q=pox[a-b-c];        ll k=1,tt;        while(A){            tt=facx(A);            k=modmul(tt,k,pox[cc]);            A=A/p;        }        while(B){            tt=infacx(B);            k=modmul(tt,k,pox[cc]);            B=B/p;        }        while(C){            tt=infacx(C);            k=modmul(tt,k,pox[cc]);            C=C/p;        }        return modmul(k,q,pox[cc]);    }};