2019-2020 ICPC North-Western Russia Regional Contest

Pro: 8/8/13

Rank: 19/112

若$p$是质数,则有$C_{n}^{m} \% p \equiv C_{n\%p}^{m\%p} \times C_{n/p}^{m/p} \%p$

一般$p\leq 10^{5}$的时候,通过预处理阶乘及其逆元可以递归计算.在算阶乘的逆元的时候,是可以线性计算的,原理为:$\frac{1}{(n-1)!}=\frac{n}{n!} \rightarrow inv_{(n-1)!}=n \times inv_{n!}$

IL void Ready(){
    reg int i=0;
    mi[0]=inv[0]=1;
    for (i=1;i<=MOD;i++)    mi[i]=(mi[i-1]*i)%MOD;
    inv[MOD-1]=Mi(MOD-1,MOD-2);
    for (i=MOD-1;i;i--) inv[i-1]=(inv[i]*i)%MOD;
}
 
IL LL C(LL n,LL m){
    return (!m)?1:(mi[n]*inv[m]%MOD)*inv[n-m]%MOD;
}
 
IL LL Lucas(LL n,LL m){
    return (!m)?1:Lucas(n/MOD,m/MOD)*C(n%MOD,m%MOD)%MOD;
}

下次一定

下次一定