组合数取模
Description
<!DOCTYPE html> <html> <head> <title>组合数取模</title> </head> <body>组合数取模
求组合数 $C(n, m) \% P ; P=10^9+7 ; C(n, m)=\frac{n !}{m !(n-m) !}$
输入格式
第一行一个整数 $T$; 表示测试数据组数。
接下来 $T$ 行, 每行两个整数 $n$ 和 $m$
输出格式
输出 $T$ 行, 表示 $C(n, m) \% P$ 的结果。
样例
输入
2
6 3
1000000 555555
输出
20
289528777
数据范围与提示
$30 \%$ 的数据, $m \leq n \leq 5000 ; T \leq 10^3$
$60 \%$ 的数据, $m \leq n \leq 10^6 ; T=1$
$100 \%$ 的数据, $m \leq n \leq 10^6 ; T \leq 10^3$
$\left(\begin{array}{l}n \\ m\end{array}\right)=\frac{n !}{m !(n-m) !}$ 。不考虑模数, 只需预处理 $n !$ 即可 $O(1)$ 计算组合数。
考虑素数模数 $p$, 由费马小定理可知, $x^{p-1} \equiv 1 \bmod p \rightarrow \frac{1}{x} \equiv x^{p-2} \bmod p$, 即 $x$ 模 $p$ 的乘法逆元与 $x^{p-2}$ 同余, 可以通过快速幂计算。
</body> </html>Source
数论统计
相关
在下列比赛中: