瞬间移动

题目连接：

http://acm.hdu.edu.cn/showproblem.php?pid=5698

Description

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

Input

多组测试数据。

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

Output

一个整数表示答案

Sample Input

4 5

Sample Output

Hint

题意

题解：

数学题先打表，写个智障dp，然后看一看

发现，哦好像是个杨辉三角

哦好像答案就是C(n+m-4,n-2)啊

交一发，诶过了

代码

#include<math.h>

#include<cstring>

#include<algorithm>

#include<stdio.h>

using namespace std;

const int maxn = 1e6+7;

const int mod = 1e9+7;

long long fac[maxn];

long long qpow(long long a,long long b)

{

    long long ans=1;a%=mod;

    for(long long i=b;i;i>>=1,a=a*a%mod)

        if(i&1)ans=ans*a%mod;

    return ans;

}

long long C(long long n,long long m)

{

    if(m>n||m<0)return 0;

    long long s1=fac[n],s2=fac[n-m]*fac[m]%mod;

    return s1*qpow(s2,mod-2)%mod;

}

int n,m;

int main()

{

    fac[0]=1;

    for(int i=1;i<maxn;i++)

        fac[i]=fac[i-1]*i%mod;

    while(scanf("%d%d",&n,&m)!=EOF)

        printf("%lld\n",C(n+m-4,n-2));

}

巴特西

HDU 5698 瞬间移动数学

瞬间移动

题目连接：

Description

Input

Output

Sample Input

Sample Output

Hint

题意

题解：

代码

最新文章

热门文章

巴特西

HDU 5698 瞬间移动 数学

瞬间移动

题目连接：

Description

Input

Output

Sample Input

Sample Output

Hint

题意

题解：

代码

最新文章

热门文章

HDU 5698 瞬间移动数学