51nod 1119 机器人走方格 V2 求大组合取模--逆元

2017年03月28日 11点热度 0人点赞 0条评论
基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题

51nod 1119 机器人走方格 V2 求大组合取模--逆元 收藏

51nod 1119 机器人走方格 V2 求大组合取模--逆元 关注
M * N的方格,一个机器人从左上走到右下,只能向右或向下走。有多少种不同的走法?由于方法数量可能很大,只需要输出Mod 10^9 + 7的结果。

Input
第1行,2个数M,N,中间用空格隔开。(2 <= m,n <= 1000000)
Output
输出走法的数量 Mod 10^9 + 7。
Input示例
2 3
Output示例

3

//注意是对n+m-2取m-1,数据范围 
#include
#include
using namespace std;
#define ll long long
const ll mod=1e9+7;
ll g;
void exgcd(ll a,ll b,ll& x,ll& y){
	if(b==0){
		x=1,y=0;
		g=a;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
int main(){
	ll n,m,a=1,b=1,x,y;
	cin>>n>>m;
	if(nn;i--)
	a=(a*i)%mod;
	for(ll i=1;i<=m;i++)
	b=(b*i)%mod;
	//关于逆元,设x为b%m的逆元,于是有x*b=1(mod m),于是问题就是求出x->x*b+k*m=1; 
	exgcd(b,mod,x,y);
	g=mod/g;
	x=(x+g)%g;
	cout<<(x*a)%mod<
未经允许不得转载!51nod 1119 机器人走方格 V2 求大组合取模--逆元

update

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