插板法求得答案為：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
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
