733 字
4 分钟
扩展Lucas定理求组合数
在求组合数的时候, 我们可能遇到模数是非质数的情况, 这时正常的Lucas可能无法解决问题。 所以我们要用到扩展Lucas定理
我们令
可得同余方程
然后我们考虑求 的值
因为
我们只要求出, ,
我们考虑如何求
以 为例
求解可以分为3部分: 第一部分是的幂的部分可以直接求解
第二部分是一个新的阶乘
发现第三部分在模意义下是以为周期的然后就可以较轻松的求出了
最后一个问题是对于求出的, 有可能与 不互质。
我们需要将 拆出来考虑就可以了
计算中质因子的个数的公式为
递推式也可以写为
pk
为 , exP
为 phip
为
long long Mul(int n, int id){ if (n == 0) return 1; long long ans = 1; if (n / pk[id]) { for (int i = 2; i <= pk[id]; i++) if (i % exP[id]) ans = ans * i % pk[id]; // ans = pow_mod(TT[id][pk[id]], n / pk[id], pk[id]); } // ans = ans * TT[id][n % pk[id]] % pk[id]; for (int i = 2; i <= n % pk[id]; i++) if (i % exP[id]) ans = ans * i % pk[id]; return ans * Mul(n / exP[id], id) % pk[id];}int exlucas(int n, int m, int id){ if (n < m || n < 0 || m < 0) return 0; if (m == n || m == 0) return 1; long long a = Mul(n, id), b = Mul(m, id), c = Mul(n - m, id); int t = 0; for (int i = n; i; i /= exP[id]) t += i / exP[id]; for (int i = m; i; i /= exP[id]) t -= i / exP[id]; for (int i = n - m; i; i /= exP[id]) t -= i / exP[id]; return a * pow_mod(b, phip[id] - 1, pk[id]) % pk[id] * pow_mod(c, phip[id] - 1, pk[id]) % pk[id] * pow_mod(exP[id], t, pk[id]) % pk[id];}long long CRT(int *a, int *b, int n){ long long N = 1, Ni, now, ans = 0; for (int i = 1; i <= n; i++) N *= a[i]; for (int i = 1; i <= n; i++) { Ni = N / a[i]; now = pow_mod(Ni, phip[i] - 1, a[i]); ans = (ans + (b[i] * now % N) * Ni % N) % N; } return ans;}long long Calc(int n, int m){ if (n < 0 || m < 0 || n < m) return 0; for (int i = 1; i <= t; i++) { b[i] = exlucas(n, m, i); } return CRT(pk, b, t);}