阶乘和阶乘逆元

Max超

发布于 2019-01-21 11:18:14

1.4K0

文章被收录于专栏：蓝桥杯历年省赛真题集蓝桥杯历年省赛真题集

瞬间移动

有一个无限大的矩形，初始时你在左上角（即第一行第一列），每次你都可以选择一个右下方格子，并瞬移过去（如从下图中的红色格子能直接瞬移到蓝色格子），求到第nn行第mm列的格子有几种方案，答案对1000000007取模。

Input

多组测试数据。

两个整数n,m(2<= n,m<=100000)

Output

一个整数表示答案

Sample Input

4 5

Sample Output

案例中的十种方案如下：

代码如下：

#include <cstdio>  
#include <cstring>  
#define ll long long  
int const MOD = 1e9 + 7;  
int const MAX = 200000;  
ll fac[MAX + 5], inv_fac[MAX + 5];  
int n, m;  
 //预处理阶乘
ll qpow(ll x, ll n)  
{  
    ll res = 1;  
    while(n)  
    {  
        if(n & 1)  
            res = (res * x) % MOD;  
        x = (x * x) % MOD;  
        n >>= 1;  
    }  
    return res;  
}  
//阶乘逆元 
void pre()  
{  
    fac[0] = 1;  
    for(int i = 1; i <= MAX; i++)  
        fac[i] = (fac[i - 1] * i) % MOD;  
    inv_fac[MAX] = qpow(fac[MAX], MOD - 2);  
    for(int i = MAX - 1; i >= 0; i--)  
        inv_fac[i] = (inv_fac[i + 1] * (i + 1)) % MOD;   
}  

int main()  
{  
    pre();  
    while(scanf("%d %d", &n, &m) != EOF)  
    {  
        ll a = fac[n + m - 4] % MOD;  
        ll b = (inv_fac[n - 2] * inv_fac[m - 2]) % MOD;  
        printf("%I64d\n", (a * b) % MOD);  
    }  
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017年02月02日，如有侵权请联系 cloudcommunity@tencent.com 删除

input