插板法求得答案为：C(n+m,m)。
直接运用lucas定理即可，只是需要预处理出阶乘值，否则会T。
1
#include <cstdio>
2
3
typedef
long
long
ll;
4
const
int
N =
100000
;
5
int
f[N];
6
7
void
init(
int
p )
8
{
9
f[
0
] =
1
;
10
for
(
int
i =
1
; i < p; i++
)
11
{
12
f[i] = (ll) f[i -
1
] * i %
p;
13
}
14
}
15
16
int
pow_mod(
int
a,
int
n,
int
mod )
17
{
18
int
ans =
1
, w = a %
mod;
19
while
( n )
20
{
21
if
( n &
1
)
22
{
23
ans = (ll) ans * w %
mod;
24
}
25
w = (ll) w * w %
mod;
26
n = n >>
1
;
27
}
28
return
ans;
29
}
30
31
int
c(
int
n,
int
m,
int
p )
32
{
33
if
( m > n )
return
0
;
34
int
ans = (ll) f[n] * pow_mod( (ll) f[n - m] * f[m] % p, p -
2
, p ) %
p;
35
return
ans;
36
}
37
38
int
lucas(
int
n,
int
m,
int
p )
39
{
40
int
ans =
1
;
41
while
( m )
42
{
43
ans = (ll) ans * c( n % p, m % p, p ) %
p;
44
n = n / p, m = m /
p;
45
}
46
return
ans;
47
}
48
49
int
main ()
50
{
51
int
t;
52
scanf(
"
%d
"
, &
t);
53
while
( t--
)
54
{
55
int
n, m, p;
56
scanf(
"
%d%d%d
"
, &n, &m, &
p);
57
init(p);
58
printf(
"
%d\n
"
, lucas( n +
m, m, p ));
59
}
60
return
0
;
61
}
