昨天學習杜教程式碼的時候看到了一個黑科技（先上程式碼讓大家感受一下）
VI
gao
(
int
n
)
{
VI
ret
(
p
+
1
,
0
);
if
(
n
==
0
)
{
ret
[
0
]
=
1
;
}
else
if
(
n
%
2
==
0
)
{
VI
c
=
gao
(
n
/
2
);
rep
(
i
,
0
,
p
+
1
)
rep
(
j
,
0
,
p
+
1
)
if
(
i
+
j
<=
p
)
ret
[
i
+
j
]
+=
c
[
i
]
*
c
[
j
];
}
else
{
VI
c
=
gao
(
n
-
1
);
rep
(
i
,
0
,
p
+
1
)
rep
(
j
,
0
,
2
)
if
(
i
+
j
<=
p
)
ret
[
i
+
j
]
+=
c
[
i
];
}
return
ret
;
}
這段程式碼返回一個vector，其第i項是C_n^i
我們知道求C_n^i 有一個經典的遞推的方法：C_n^i = C_n^{i - 1} * \frac{n - i + 1} {i}
這種方法因為有除法，在要模的數是一個合數的時候就不適用了
此時，通常的做法就是根據上述公式每次暴力求i和前面那些項的gcd，然後除掉，我也一直是這樣寫的，
直到昨天看到杜教的程式碼……
