2016"百度之星" - 初赛（Astar Round2B）1003 瞬间移动(HDU5698)(逆元+快速幂）

叁歲伎倆 2022-08-22 13:20 130阅读 0赞

# **2016”百度之星” - 初赛（Astar Round2B）1003 瞬间移动(HDU5698)(逆元+快速幂）** #

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

--------------------

## Problem Description ##

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

![题目示意图][20160528221818037]

--------------------

**Input**  
多组测试数据。

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

**Output**  
一个整数表示答案

**Sample Input**

> 4 5

**Sample Output**

> 10

**Source**  
2016”百度之星” - 初赛（Astar Round2B）

题目在这里：[题目链接][Link 1]

--------------------

**假设到第(n,m)个格子的方法数为s(n,m)**

**则s(n,m)等于他与起始位置所夹的矩形内的各个格子方法数之和，即** s(n,m)=∑n−1i=2∑m−1j=2s(i,j)

**不难发现s(n,m)等于s(n-1,m)+s(n,m-1)，即答案是一个斜着的杨辉三角**

**问题便转换为组合数求模，费马小定理，快速幂求逆元，**

**预处理阶乘和逆元**

--------------------

代码：

#include<stdio.h>
    #define max 200005
    #define mod 1000000007
    int n,m;
    long long j[max];           
    long long p[max];           
    
    long long ksm(long long a,long long b)
    {
        long long ans,base;
        ans=1;
        base=a%mod;
        while(b)
        {
            if(b&1)
                ans=ans*base%mod;
            base=base*base%mod;
            b>>=1;
        }
        return ans;
    }
    
    void init()
    {
        j[1]=1;
        p[1]=1;
        for(int i=2;i<=max;i++)
        {
            j[i]=(i*j[i-1])%mod;
            p[i]=ksm(j[i],mod-2);
        }
    }
    
    int main()
    {
        init();
        while(~scanf("%d %d",&n,&m))
        {
            if(n==2||m==2)
            {
                printf("1\n");
                continue;
            }
            printf("%lld\n",j[n+m-4]%mod*p[m-2]%mod*p[n-2]%mod);
        }
        return 0;
    }

[20160528221818037]: /images/20220722/7f545b30076c477283c0847bd90fdceb.png
[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=5698