HDU5698 瞬间移动(求逆元)

Problem Description

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

Input

多组测试数据。

两个整数n,m(2≤n,m≤100000)

Output

一个整数表示答案

Sample Input

4 5

Sample Output

10

思路

我们要从(1,1)$(1,1)$点走到(n,m)$(n,m)$点，只能向右下角的格子里走，那么(1,1)$(1,1)$所在的行和列不能走,(n,m)$(n,m)$所在的行和列不能走，那么能走的面积就是(n−2)∗(m−2)$(n-2)\ast (m-2)$这么大的面积，行和列分别考虑，实质上就是求组合数Cn−2(n−2)+(m−2)$C_{(n-2)+(m-2)}^{n-2}$

因为Cmn=n!m!∗(n−m)!$C_n^m=\frac{n!}{m!\ast (n-m)!}$,乘以一个数等于乘这个数的逆元，我们先预处理出阶乘的逆元。

首先求出一个数模p的逆元:

f[i]=(p−pi)∗f[p%i]%p$$f[i]=(p-\frac{p}{i})\ast f[p\mathrm{\%}i]\mathrm{\%}p$$

然后再递推出n!$n!$的逆元

inv[(n−1)!]=inv[n!]∗n%p$$inv[(n-1)!]=inv[n!]\ast n\mathrm{\%}p$$

可以得到

inv[n!]=inv[(n−1)!]∗f[n]%p$$inv[n!]=inv[(n-1)!]\ast f[n]\mathrm{\%}p$$

然后就可以求出组合数了

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll N=200000+20;
ll fac[N]= {1,1},inv[N]= {1,1},f[N]= {1,1};
/*
fac[i]:i的阶乘
inv[i]:i的阶乘的逆元
f[i]:i的逆元
*/
ll C(ll a,ll b)//除以一个数等于乘这个数的逆元
{
    return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
void init()
{
    for(ll i=2; i<N; i++)
    {
        fac[i]=fac[i-1]*i%mod;
        f[i]=(mod-mod/i)*f[mod%i]%mod;
        inv[i]=inv[i-1]*f[i]%mod;
    }
}

int main()
{
    ll n,m;
    init();
    while(cin>>n>>m)
        cout<<C(m+n-4,m-2)<<endl;
    return 0;
}