Lucas定理（大数组合数取模）

2019-04-14 12:01发布

站内文章 / 模拟电子
12050 0 1305
Lucas定理可以用来求大数组合数取模。 LL f[200000]; void init(int p) { f[0] = 1; for(int i = 1; i <= p; ++i) f[i] = f[i-1] * i % p; } LL pow_mod(LL a, LL x, int p) { LL ret = 1; a %= p; while(x) { if(x & 1) { ret = ret * a % p; --x; } else { a = a * a % p; x >>= 1; } } return ret; } LL Lucas(LL n, LL k, int p) { LL ret = 1; while(n && k) { LL nn = n % p, kk = k % p; if(nn < kk) return 0; ret = ret * f[nn] * pow_mod(f[kk] * f[nn - kk] % p, p - 2, p) % p; n /= p; k /= p; } return ret; }

热门文章