昨天学习杜教代码的时候看到了一个黑科技（先上代码让大家感受一下）
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，然后除掉，我也一直是这样写的，
直到昨天看到杜教的代码……
