百度之星2016练习赛瞬间移动

左手的ㄟ右手 2022-08-22 14:16 154阅读 0赞

[瞬间移动][Link 1] ![ok.png][]

![08D30FABE0EF50B50000000000000013.png][]

[System Message][] (命题人)

基准时间限制：1 秒 空间限制：131072 KB 分值: 80

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

![08D2E44A738D4F45000000000000007B.png][]

Input

单组测试数据。
    两个整数n,m（2<=n,m<=100000）

Output

一个整数表示答案。

Input示例

4 5

Output示例

<pre name="code" class="cpp">#include<cstdio>
    #include<cstring>
    const long long mod=1000000007;
    typedef long long ll;
    const int N=100002;
    ll inv[N];
    int main()
    {
        int n,m;
        inv[1]=1;
        for(int i=2;i<N;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        while(~scanf("%d%d",&n,&m)){
            if(n==1||m==1){
                printf("0\n");continue;
            }
            n=n+m-4;
            m=m-2;
            ll ans=1;
            for(int i=1;i<=m;i++){
                ans=(ans*(ll)(n-i+1))%mod;
                ans=(ans*inv[i])%mod;
            }
            printf("%lld\n",ans);
        }
        return 0;
    }

[Link 1]: http://www.51nod.com/contest/problem.html#!problemId=1627
[ok.png]: http://file.51nod.com/images/icon/ok.png
[08D30FABE0EF50B50000000000000013.png]: http://img.51nod.com/ti_40_40/upload/000FBF9C/08D30FABE0EF50B50000000000000013.png
[System Message]: http://www.51nod.com/contest/user.html#!userId=3263
[08D2E44A738D4F45000000000000007B.png]: /images/20220722/afbc29fc20a14fa9a78ecd238ac333ed.png