扩展卢卡斯定理模板 / p4720

前言

扩展卢卡斯算法可以解决 C n m % m o d C_n^m \% mod Cnm​%mod，mod 不是素数的问题

可以在 O ( m o d ( log ⁡ m o d ) ) O(mod(\log mod)) O(mod(logmod))时间内处理 1 e 18 1e18 1e18 的 m 和 n

一、题目

题目链接 洛谷P4720

二、思路及代码 1.思路

可以利用中国剩余定理，只需求 ( m n ) ≡ r i ( m o d p k ) \dbinom{m}{n}\equiv r_i \pmod{p^k} (nm​)≡ri​(modpk) 即可 利用威尔逊定理和逆元、快速幂的知识，转化为求： n ! q x m ! q y ( n − m ) ! q z q x − y − z ( m o d q k ) \displaystyle \frac{\frac{n!}{q^x}}{\frac{m!}{q^y}\frac{(n-m)!}{q^z}}q^{x-y-z} \pmod{q^k} qym!​qz(n−m)!​qxn!​​qx−y−z(modqk) 不是很好理解，留下板子即可

2.代码

代码如下：

#include 
#define int long long
using namespace std;
int n, m, mod;
int quickpow(int base, int x, int p) {
  int ans = 1;
  while (x) {
    if (x & 1) ans = ans * base % p;
    base = base * base % p;
    x >>= 1;
  }
  return ans;
}
int exgcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  int r = exgcd(b, a % b, x, y);
  int t = x;
  x = y;
  y = t - a / b * y;
  return r;
}
int inv(int a, int b) {
  int x, y;
  return exgcd(a, b, x, y) == 1 ? (x + b) % b : -1;
}
int CRT(int x, int ps) { return x * inv(mod / ps, ps) % mod * mod / ps % mod; }
int fac(int x, int ps, int p) {  // ps = p ^ k
  if (!x) return 1;
  int res = 1;
  for (int i = 2; i