====== 本周训练 ======

[[2020-2021:teams:tle233:NWRussia2019|2019-2020 ICPC North-Western Russia Regional Contest]]

Pro: 8/8/13

Rank: 19/112 

====== 本周推荐 ======


===== Marvolo =====


==== Lucas定理 ====

若$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!} -> inv_{(n-1)!}=n \times inv_{n!}$

==== 模板 ====

<code cpp>
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;
}
</code>

===== Kevin =====

下次一定

===== TangYan =====

下次一定