组合数学 中国剩余定理 整理

扩展Lucas略解

Posted by Dispwnl on February 13, 2019

$a.$

要求$C_{n}^{m}\%p​$的值，如果$p​$是质数，可以用$Lucas​$定理$O(\log n)​$解决

但是如果$p$不是质数怎么做呢

预处理阶乘然后O(1)出解

这里就需要用到扩展$Lucas$定理了

$b.$

可以把$p$拆成$p_1^{k_1}\times p_2^{k_2}\times …\times p_l^{k_l}$，其中$p_i$为质因数

假设答案为$x$，则有 \(\left\{\begin{matrix}x\equiv a_1\pmod{p_1^{k_1}} \\x\equiv a_2\pmod{p_2^{k_2}} \\... \\x\equiv a_l\pmod{p_l^{k_l}} \end{matrix}\right.\)

$p_i^{k_i}​$之间互质！所以如果知道$a_i$，可以用$crt$求出$x$

$a_i​$就是在$\%p_i^{k_i}$意义下$C_{n}^{m}$的值

问题转换成了如何求$C_{n}^{m}\%p_i^{k_i}$

$c.$

我们知道，$C_{n}^{m}\%p_i^{k_i}=\frac{n!}{m!(n-m)!}\%p_i^{k_i}$

如果$n!,m!,(n-m)!$和$\%p_i^{k_i}$互质的话，可以分别求出$n!\%p_i^{k_i},m!\%p_i^{k_i},(n-m)!\%p_i^{k_i}$的值然后逆元搞搞就行了

所以去掉$n!,m!,(n-m)!$中所有的$p$使得与$p_i^{k_i}$互质，最后再乘上去掉的$p$即可

$n!$中质因子$p$的个数为$\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+…$

$d.$

现在要求的东西只剩下$n!\%p_i^{k_i}$了

设答案为$F(n)$

用$G(n)$表示$\prod_{j=1,p_i\nmid j}^{n}j\%p_i^{k_i}$

如果$n<p_i​$，这时候$F(n)=G(n)​$

否则可以发现在$n$中长度为$p_i^{k_i}$的数的乘积是循环的，可以处理出来循环节答案$x_1=G(p_i^{k_i}-1)^{\left\lfloor\frac{n}{p_i^{k_i}}\right\rfloor}$

还有$p_i$的倍数，这个可以预先处理出来，答案就是$x_2=F(\left\lfloor\frac{n}{p_i}\right\rfloor)$

还有一部分构不成循环节的，个数不超过$p_i^{k_i}$个，所以直接暴力计算即可，答案为$x_3=G(n\%p_i^{k_i})$

所以$F(n)=x_1+x_2+x_3$

这样就求出$n!\%p_i^{k_i},m!\%p_i^{k_i},(n-m)!\%p_i^{k_i}$的值了

$e.$

逆元部分

int exgcd(int a,int b,int &x,int &y)
{
    if(!b) return x=1,y=0,a;
    int ans=exgcd(b,a%b,x,y),tt=x;
    return x=y,y=tt-1ll*a/b*y,ans;
}
int inv(int a,int b)
{
    int x,y;
    return exgcd(a,b,x,y),(x%b+b)%b;
}

快速幂部分

int Pow(int a,int b,int mod)
{
    int ans=1;
    for(;b;b>>=1,a=1ll*a*a%mod)
      if(b&1) ans=1ll*ans*a%mod;
    return ans;
}

计算$n!\%p_i^{k_i}$部分

int Cal(int n,int p,int pk)
{
    if(!n) return 1;
    int ans=1;
    for(int i=2;i<=pk;++i)
      if(i%p) ans=1ll*ans*i%pk;
    ans=Pow(ans,n/pk,pk);
    for(int i=2,L=n%pk;i<=L;++i)
      if(i%p) ans=1ll*ans*i%pk;
    return 1ll*ans*Cal(n/p,p,pk)%pk;
}

计算/处理阶乘+$crt$部分

int C(int n,int m,int p,int pk)
{
    if(m>n) return 0;
    int _A=Cal(n,p,pk),_B=Cal(m,p,pk),_C=Cal(n-m,p,pk),k=0;
    LL _=_P_/pk;
    for(int i=n;i;i/=p)
      k+=i/p;
    for(int i=m;i;i/=p)
      k-=i/p;
    for(int i=n-m;i;i/=p)
      k-=i/p;
    return 1ll*_A*inv(_B,pk)%pk*inv(_C,pk)%pk*Pow(p,k,pk)%pk*_%_P_*inv(_,pk)%_P_;
}
FRIENDS