from yangboy
Lucas定理
A、B是非负整数，p是质数。A B写成p进制：A=a[n]a[n-1]...a[0]，B=b[n]b[n-1]...b[0]。
则组合数C(A,B)与C(a[n],b[n])*C(a[n-1],b[n-1])*...*C(a[0],b[0]) mod p同余
即：Lucas(n,m,p)=C(n%p,m%p)*Lucas(n/p,m/p,p)
//快速幂a^b % k
- ll PowerMod(ll a, ll b, ll k) {
- ll tmp = a, ret = 1;
- while (b) {
- if (b & 1) ret = ret * tmp % k;
- tmp = tmp * tmp % k;
- b >>= 1;
- }
- return ret;
- }
//求C(n, m)%p p最大为10^5 n, m可以很大！
- ll Lucas(ll n, ll m, ll p) {
- ll ret = 1;
- while (n && m) {
- ll nn = n%p, mm = m%p;
- if (nn < mm) return 0;
- //fac[nn]为预处理的 fac[n] = n!%p
- ret = ret*fac[nn]*PowerMod(fac[mm]*fac[nn-mm]%p, p-2, p)%p;
- n /= p;
- m /= p;
- }
- return ret;
- }
- //C(n, m) % p
- Lucas(n, m, p);
AC代码：
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <iostream>
- using namespace std;
- typedef long long ll;
- ll fac[100003];
- void init(ll p) {
- fac[0] = 1;
- for (int i=1; i<=p; i++) fac[i] = fac[i-1]*i%p;
- }
- ll PowerMod(ll a, ll b, ll k) {
- ll tmp = a, ret = 1;
- while (b) {
- if (b & 1) ret = ret * tmp % k;
- tmp = tmp * tmp % k;
- b >>= 1;
- }
- return ret;
- }
- ll Lucas(ll n, ll m, ll p) {
- ll ret = 1;
- while (n && m) {
- ll nn = n%p, mm = m%p;
- if (nn < mm) return 0;
- ret = ret*fac[nn]*PowerMod(fac[mm]*fac[nn-mm]%p, p-2, p)%p;
- n /= p;
- m /= p;
- }
- return ret;
- }
- int main() {
- int T;
- ll n, m, p;
- cin >> T;
- while (T--) {
- cin >> n >> m >> p;
- init(p);
- cout << Lucas(n+m, m, p) << endl;
- }
- return 0;
- }