http://acm.hdu.edu.cn/showproblem.php?pid=3037

Lucas定理模板。

现在才写，noip滚粗前兆QAQ

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int jc[100003];

int p;

int ipow(int x, int b) {

	ll t = 1, w = x;

	while (b) {

		if (b & 1) t = t * w % p;

		w = w * w % p;

		b >>= 1;

	}

	return (int) t;

}

int Lucas(int n, int m) {

	int a, b, ret = 1;

	while (n && m) {

		a = n % p; b = m % p;

		if (a < b) return 0;

		ret = (int) (1ll * ret * jc[a] % p * ipow((int) (1ll * jc[a - b] * jc[b] % p), p - 2) % p);

		n /= p; m /= p;

	}

	return ret;

}

int main() {

	int T, n, m;

	scanf("%d", &T);

	while (T--) {

		scanf("%d%d%d", &n, &m, &p);

		jc[0] = 1;

		for (int i = 1; i < p; ++i)

			jc[i] = (int) (1ll * jc[i - 1] * i % p);

		printf("%d\n", Lucas(n + m, n));

	}

	return 0;

}