HDU 3037 卢卡斯定理

        卢卡斯定理求组合数  C ( N, M ) % P，当 P 是素数时适用，这里可以当一个模板用  HUD 3037

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SIZE = 100231;
LL F[SIZE];

void init(LL Mod) {
	F[0] = 1;
	for (int pos = 1; pos <= Mod; pos++)
		F[pos] = F[pos - 1] * pos % Mod;
}

LL inv(LL A, LL M) {
	return A == 1 ? 1 : inv(M % A, M) * (M - M / A) % M;
}

LL Lucas(LL N, LL M, LL Mod) {
	init(Mod);
	LL ans = 1;
	while (N && M) {
		LL A = N % Mod, B = M % Mod;
		if (A < B)
			return 0;
		ans = ans * F[A] % Mod * inv(F[B] * F[A - B] % Mod, Mod) % Mod;
		N /= Mod; M /= Mod;
	}
	return ans;
}

int main() {
    ios::sync_with_stdio(false);
	int quan; cin >> quan;
	LL N, M, Mod;
	while (quan--) {
		cin >> N >> M >> Mod;
		cout << Lucas(N + M, N, Mod) << endl;
	}
}