本来不打算写了的,,,但是感$jio$理解起来还是有点儿难度的来着,,,$so$还是瞎写点儿趴$QAQ$
$exLucas$主要有三步:
1)唯一分解$mod$并预处理$p^{k}$以内的阶乘
2)计算组合数并计算$p$的个数
3)用$crt$合并答案
$umm$大概具体港下,,,$QAQ$
就首先拆下,$mod=\prod_{i=1}^{m} p_{i}^{c_i}$
然后对组合数,$\binom{n}{m}=\frac{n!}{m!\cdot (n-m)!}$,对每个$p_{i}^{c_i}$做一遍,最后用$crt$就好
具体来说,首先显然考虑的是对$n!$,$m!$,$(n-m)!$质因数分解,但是这儿要注意的是显然$p$的倍数的存在会导致一些乱七八糟的存在,所以对$p$的倍数单独处理下
对每个$p$,首先搞出$n!$,$m!$,$(n-m)!$内分别有多少个$p$的倍数,设数量为$f[i]$,则有$f[i]=f[i/p]+i/p$,听起来有点儿像$Lucas$,,,?大概意会下,就说首先这个范围内会有i/p个,但要注意的是有可能存在麻油被赶尽杀绝的,,,比如,$p^{2}$,$p^{3}$这样儿的,$so$还要继续做下去,就是$f[i/p]$.然后就可以求出,$p$的倍数有$f_{n}-f_{m}-f_{n-m}$个,这个单独快速幂下
然后对于剩下的,因为$x\cdot p+y\equiv y$,所以考虑每$p^c$个分一组,就只要做出一组,剩下的都一样儿,矩阵快速幂就好
最后$crt$合并下就欧克辣
综上,$exLucas$主要需要的就是$exgcd$和$crt$,会了这两个之后再尝试理解下打下代码应该还是麻油太难的$QwQ$
放下练手题,,,
[ ]方程
[ ]古代猪文
[ ]礼物
$tbc.$
($umm$我知道讲得还是不太清楚,,,等有时间$upd$下有条理地梳理下$exLucas$的步骤趴$QwQ$