题目背景
这是一道模板题。
题目描述
给定n,m,p(1\le n,m,p\le 10^51≤n,m,p≤105)
求 C_{n+m}^{m}\ mod\ pCn+mm? mod p
保证P为prime
C表示组合数。
一个测试点内包含多组数据。
输入格式
第一行一个整数T(T\le 10T≤10)，表示数据组数
第二行开始共T行，每行三个数n m p，意义如上
输出格式
共T行，每行一个整数表示答案。
输入输出样例
输入 #1复制
2 1 2 5 2 1 5
输出 #1复制
3 3
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
inline ll qpow(ll a, ll b, ll p){if(b == 1) return a;ll t = qpow(a, b/2, p);t = t * t % p;if(b & 1) t = t * a % p;return t;
}
inline ll C(ll n, ll m, ll p){if(n < m) return 0;if(m > n - m) m = n - m;ll a = 1, b = 1;for(int i = 0;i < m;i++){a = (a * (n - i)) % p;b = (b * (i + 1)) % p;}return a * qpow(b, p-2, p) % p;
}
inline ll Lucas(ll n, ll m ,ll p){if(m == 0) return 1;return Lucas(n / p,m / p, p) * C(n % p,m % p, p) % p;
}
int main() {int t;scanf("%d", &t);while(t--) {ll n, m, p;scanf("%lld%lld%lld", &n, &m, &p);ll sum = (Lucas(n + m, n, p) % p);printf("%lld\n", sum);}return 0;
}