瞬间移动
Accepts: 1018 Submissions: 3620 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Problem Description
有一个无限大的矩形,初始时你在左上角(即第一行第一列),每次你都可以选择一个右下方格子,并瞬移过去(如从下图中的红色格子能直接瞬移到蓝色格子),求到第nn行第mm列的格子有几种方案,答案对10000000071000000007取模。
Input
多组测试数据。
两个整数n,m(2\leq n,m\leq 100000)n,m(2≤n,m≤100000)
Output
一个整数表示答案
Sample Input
4 5
Sample Output
10
//通过递推可以知道这是杨辉三角的转化,所得的值为C(n+m-4,m-2);
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define ll long long
#define N 200010
#define M 1000000007
using namespace std;
ll s[N];
void init()
{
s[0]=1;
for(int i=1;i<=N;i++)
{
s[i]=s[i-1]*i%M;
}
}
ll ks(ll n,ll k)
{
ll s=1;
while(k)
{
if(k&1)
s=s*n%M;
n=n*n%M;
k>>=1;
}
return s;
}
ll C(ll n,ll k)
{
ll a=s[n];
ll b=s[k]*s[n-k]%M;
ll p=ks(b,M-2);
return a*p%M;
}
int main()
{
ll n,m;
init();
while(scanf("%lld%lld",&n,&m)!=EOF)
{
ll ans=C(n+m-4,m-2);
printf("%lld\n",ans);
}
return 0;
}