扩展 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;
}