扩展Lucas定理

蛮怪的

概述:

与BSGS和CRT的扩展类似, 由于$p$不为质数时Lucas定理的部分证明会失效, 所以不能直接使用Lucas定理.

但与之不同的是, 扩展Lucas与Lucas定理其实一点关系也没有(蛮怪的).

实现:

假设将$p$进行质因数分解, 得到:

$$p = q_1^{k_1}q_2^{k_2} ... q_t^{k_t}$$

然后列出同余方程组:

$$\begin{cases} {n \choose m} \equiv b_1(mod\ q_1^{k_1}) \\ {n \choose m} \equiv b_2(mod\ q_2^{k_2}) \\ \vdots \\ {n \choose m} \equiv b_t(mod\ q_t^{k_t}) \\ \end{cases}$$

使用CRT求出这个同余方程组的解即可求得模$p$意义下的唯一解, 即${n \choose m }\ mod\ p$

现在要解决的问题是如何求出${n \choose m }\ mod\ q_i^{k_i}$.

显然:

$$\begin{aligned} & {n \choose m }\ mod\ q_i^{k_i} \\ = & \frac{n!}{m!(n-m)!}\ mod\ q_i^{k_i} \end{aligned}$$

但是$m!$与$(n-m)!$不一定与$q_i^{k_i}$互质, 所以没法直接求.

考虑将式中所有的$q_i$因子提出来, 则上式变为:

$$\frac{\frac{n!}{q_i^x}}{\frac{m!}{q_i^y}\frac{(n-m)!}{q_i^z}} \times q_i^{x-y-z}\ mod\ q_i^{k_i}$$

由于我们将所有的$q_i$因子提出来了, 所以此时的$\frac{m!}{q_i^y}$和$\frac{(n-m)!}{q_i^z}$与$q_i^{k_i}$互质, 便可以求逆元了.

于是问题转化为求:

$$\frac{n!}{q_i^x}\ mod\ q_i^{k_i}$$

将$n!$展开, 有:

$$\begin{aligned} n! & = 1 \cdot 2 \cdot ... \cdot n \\ & = (q_i \cdot 2q_i \cdot ...)(1 \cdot 2 \cdot ...) \end{aligned}$$

左边是被$q_i$整除的数, 右边则相反.

易知左边有$\lfloor \frac{n}{q_i} \rfloor$项, 则:

$$\begin{aligned} n! & = q_i^{\lfloor \frac{n}{q_i} \rfloor} (\lfloor \frac{n}{q_i} \rfloor)!(\prod_{j=1,q_i \nmid j}^{n}j) \end{aligned}$$

同时后面这串连乘在$mod\ q_i^{k_i}$下是循环的, 有:

$$\begin{aligned} & n! \\ \equiv & q_i^{\lfloor \frac{n}{q_i} \rfloor} (\lfloor \frac{n}{q_i} \rfloor)!(\prod_{j=1,q_i \nmid j}^{q_i^{k_i}}j)^{\lfloor \frac{n}{q_i^{k_i}} \rfloor} \\ & (\prod_{j=q_i^{k_i}{\lfloor \frac{n}{q_i^{k_i}} \rfloor},q_i \nmid j}^{n}j)(mod\ q_i^{k_i}) \end{aligned}$$

前面的连乘是循环节, 而后面的是余项.

同时中间的$(\lfloor \frac{n}{q_i} \rfloor)!$也有可能含有$q_i$因子, 所以定义:

$$f(n) = \frac{n!}{p^x}\ mod\ p^k$$

其中$p$为质数, $x$为$n!$中因子$p$的次数.

由上述讨论可得:

$$\begin{aligned} f(n) \equiv & f(\lfloor \frac{n}{p} \rfloor)(\prod_{j=1,q_i \nmid j}^{q_i^{k_i}}j)^{\lfloor \frac{n}{q_i^{k_i}} \rfloor} \\ & (\prod_{j=q_i^{k_i}{\lfloor \frac{n}{q_i^{k_i}} \rfloor},q_i \nmid j}^{n}j)(mod\ p^k) \end{aligned}$$

递归处理即可, 边界条件为$f(0)=1$时间复杂度为$O(log_pn)$

最后还有一个问题: $\frac{n!}{p^x}$中的$x$是多少, 因为我们要求$p^{x-y-z}$.

同样可以通过递归的方法求得, 设$g(n)$即为上述的次数, 则由上面的讨论:

$$g(n) = \lfloor \frac{n}{p} \rfloor+g(\lfloor \frac{n}{p} \rfloor)$$

边界条件是$g(n)=0, n < p$.

至此所有的细节就已经介绍完了.

代码:

typedef long long LL;
LL ksm(LL a,LL b,LL p); //快速幂(a^b mod p)
LL inv(LL x,LL p); //逆元(exgcd)
LL fp(LL n,LL p,LL pk) {  //求f(n)
    if(n==0) {  //边界
        return 1;
    }
    LL lop(1);  //循环节
    for(int i(1);i<pk;++i) {
        if(i%p!=0) {
            lop = lop*i%pk;
        }
    }
    lop = ksm(lop,n/pk,pk);
    LL rem(1);  //余项
    for(LL i(pk*(n/pk));i<=n;++i) {
        if(i%p!=0) {
            rem = (__int128)rem*i%pk; //防止溢出
        }
    }
    return fp(n/p,p,pk)*lop%pk*rem%pk;
}
LL gp(LL n,LL p) {  //求g(n)
    if(n<p) {
        return 0;
    } else {
        return gp(n/p,p)+(n/p);
    }
}
LL cpk(LL n,LL m,LL p,LL pk) {  //求C mod p^k
    LL np=fp(n,p,pk), mp=fp(m,p,pk), nmp=fp(n-m,p,pk), pp=gp(n,p)-gp(m,p)-gp(n-m,p);
    return np*inv(mp,pk)%pk*inv(nmp,pk)%pk*ksm(p,pp,pk)%pk;
}
LL a[55],b[55]; //x = b_i (mod a_i), CRT
LL exLucas(LL n,LL m,LL p) {
    LL tmp(p);
    int pcnt(0);
    for(int i(2);i<=p;++i) {
        if(tmp%i==0) {  //找到一个质因数
            a[++pcnt] = 1;
            while(tmp%i==0) {
                tmp /= i;
                a[pcnt] *= i;
            }
            b[pcnt] = cpk(n,m,i,a[pcnt]);
        }
        if(tmp==1) {
            break;
        }
    }
    LL ret(0);
    for(int i(1);i<=pcnt;++i) { //CRT
        ret = (ret+(b[i]*(p/a[i])%p*inv(p/a[i],a[i])%p))%p;
    }
    return ret;
}