本文共 943 字，大约阅读时间需要 3 分钟。
解题思路：
直接求C(n+m , m) % p , 由于n , m ,p都非常大，所以要用Lucas定理来解决大组合数取模的问题。
#include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long#define FOR(i, x, y) for(int i=x;i<=y;i++)using namespace std;const int maxn = 100000 + 10;LL Pow_mod(LL a, LL b, LL mod){ LL ret = 1; while(b) { if(b & 1) ret = ret * a % mod; a = a * a % mod; b >>= 1; } return ret;}LL fac[maxn];void init(LL p){ fac[0] = 1; FOR(i, 1, p) fac[i] = (fac[i-1] * i) % p;}LL Lucas(LL n, LL m, LL p){ LL ret = 1; while(n && m) { LL a = n % p, b = m % p; if(a < b) return 0; ret = (ret * fac[a] * Pow_mod(fac[b] * fac[a-b] % p , p - 2 , p)) % p; n /= p, m /= p; } return ret;}int main(){ int T; scanf("%d",&T); while(T--) { int n, m, p; scanf("%d%d%d", &n, &m, &p); init(p); printf("%d\n", (int)Lucas(n + m, m, p)); } return 0;}
转载地址：http://mkxex.baihongyu.com/