链接：http://acm.fzu.edu.cn/problem.php?pid=2020
$Time\;Limit:\;1000\;ms$
$Memory\;Limit:\;37268\;kB$
给出组合数$C(n,m)$, 表示从$n$个元素中选出$m$个元素的方案数。例如$C(5,2)=10$, $C(4,2) = 6$.可是当$n,m$比较大的时候，$C(n,m)$很大！于是$xiaobo$希望你输出 $C(n,m)\;mod\;p$的值！
输入数据第一行是一个正整数T,表示数据组数$ (T \le 100)$ 接下来是T组数据，每组数据有$3$个正整数 $n, m, p (1 \le m \le n \le 10^9, m \le 10^4, m < p < 10^9, p是素数)$
对于每组数据，输出一个正整数，表示$C(n,m)\;mod\;p$的结果。
2
5 2 3
5 2 61
1
10
$Lucas$定理
\[\begin{pmatrix} m\\n \end{pmatrix} = \prod^k_{i=0} \begin{pmatrix} m_i\\n_i \end{pmatrix}(mod\;p) \tag{1}\] \[m=m_kp^k+m_{k-1}^p{k-1}+\cdots+m_1p+m_0 \tag{2}\] \[n=n_kp^k+n_{k-1}^p{k-1}+\cdots+n_1p+n_0 \tag{3}\]则有 \(\begin{pmatrix} p\\n \end{pmatrix} =\frac {p\cdot(p-1)\cdots(p-n+1)} {n\cdot(n-1)\cdots1} \tag{4}\)
可得 \(ans= \prod^n_{i=0}\frac{(m-n+i)}{i} \tag{5}\) 又由于取模不能进行除法，则需要求逆元，即 \(ans= \prod^n_{i=0}(m-n+i)\cdot inv(i) \tag{6}\) 由费马小定理 \(a^{p-1}\equiv 1(mod\; p) \tag{7}\) 则有 \(a^{p-1}=a\cdot a^{p-2}=1(mod\;p) \tag{8}\) 则 \(inv(a)=a^{p-2}\tag{9}\) 然后求解即可
//Time: 421ms Memory: 196kB
#include <iostream>
using namespace std;
#define ll long long
ll qpow(ll n, ll m, ll p)
{
ll res = 1;
n %= p;
while(m)
{
if(m & 1) res = res * n % p, --m;
m >>= 1;
n = n * n % p;
}
return res;
}
ll C(ll n, ll m, ll p)
{
if(m > n) return 0;
ll res = 1;
for(int i = 1; i <= m; ++i) res = res * ((n + i - m) % p * qpow(i % p, p - 2, p) % p) % p;
return res;
}
int main()
{
int t; ll n, m, p;
cin >> t;
while(t--)
{
cin >> n >> m >> p;
cout << C(n, m, p) << endl;
}
return 0;
}