AcWing - 求组合数 II(预处理&逆元)-白红宇

AcWing - 求组合数 II(预处理&逆元)

阅读量：1999 次

发布时间：2019-04-28

本文共 1081 字，大约阅读时间需要 3 分钟。

题目链接:

时/空限制：1s / 64MB

题目描述

给定n组询问，每组询问给定两个整数a，b，请你输出 $C_{a}^{b}\ mod\ (10^9+7)$ 的值。

输入格式

第一行包含整数n。

接下来n行，每行包含一组a和b。

输出格式

共n行，每行输出一个询问的解。

数据范围

1≤n≤10000,
1≤b≤a≤10^5

输入样例

3
3 1
5 3
2 2

输出样例

3
10
1

解题思路

题意:求出 $C_{a}^{b}\ mod\ (10^9+7)$ 的值。

思路:范围小的话可以通过递推求出，否则就要先预处理。首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]，如果取模的数是质数，可以用费马小定理求逆元。

由 $C_{a}^{b}=\frac{a!}{b!*(a-b)!}$ ,我们可以令 $fact[i]=i!\ mod\ 10^9+7$ ， $infact[i]=(i!)^{-1}\ mod\ 10^9+7$ ，则 $C_a^b=fact[a] * infact[b] * infact[a - b]$ 。

Accepted Code:

/*  * @Author: lzyws739307453  * @Language: C++  */#include 
   
    using namespace std;const int MAXN = 1e5, MAXM = 1e5 + 5;const int MOD = 1e9 + 7;int fact[MAXM], infact[MAXM];int Fast_Power(int a, int b, int p) {    int res = 1;    while (b) {        if (b & 1)            res = 1ll * res * a % p;        a = 1ll * a * a % p;        b >>= 1;    }    return res;}void Com_Num(int n) {	fact[0] = infact[0] = 1;    for (int i = 1; i <= n; i++) {		fact[i] = 1ll * fact[i - 1] * i % MOD;		infact[i] = 1ll * infact[i - 1] * Fast_Power(i, MOD - 2, MOD) % MOD;	}}int main() {    int t;    Com_Num(MAXN);    scanf("%d", &t);    while (t--) {        int a, b;        scanf("%d%d", &a, &b);        printf("%lld\n", 1ll * fact[a] * infact[b] % MOD * infact[a - b] % MOD);    }    return 0;}

转载地址：http://eubtf.baihongyu.com/

你可能感兴趣的文章