大组合数取模hdu5698 瞬间移动

2017年08月09日 12点热度 0人点赞 0条评论

瞬间移动

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1301    Accepted Submission(s): 620


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

大组合数取模hdu5698 瞬间移动
 


Input
多组测试数据。

两个整数n,m(2n,m100000)

 


Output
一个整数表示答案
 


Sample Input

4 5
 


Sample Output

10

#include
#include
using namespace std;
#define ll long long
const int C=1000000007;
int n,m;
ll f[200005];
ll fast_pow(ll a,ll b){  
    //求解(a^b)%C的值  
    ll ans=1;  
    while(b){  
        if(b&1) ans=(ans*a)%C;  
        b>>=1;  
        a=(a*a)%C;  
    }  
    return ans;
}
int main(){
	f[0]=1;
	for(int i=1;i<=200000;++i)
	f[i]=(f[i-1]*i)%C;
	while(~scanf("%d%d",&n,&m))
	printf("%lldn",f[n+m-4]*fast_pow(f[m-2],C-2)%C*fast_pow(f[n-2],C-2)%C);
	return 0;
}
未经允许不得转载!大组合数取模hdu5698 瞬间移动

update

纸上得来终觉浅, 绝知此事须躬行。