汕头市队赛SRM 16 A-1

A-1 SRM 16

描述

     问从(0,0)出发每一步可以向上走或者向右走，走到(n,m)的方案数有多少种？

输入格式

     两个用空格隔开的整数n和m (mod 1e9+7)。

输出格式

     一个整数，表示方案数。

样例输入

1 2

样例输出

3

数据范围与约定

对于100%的数据: n <= 1e5, m <= 1e5

样例解释

     1 先向右走，然后一直往上走

     2 先往上走，再往右走，最后再往上

     3 先一直往上走，再往右走

诶呦

一道套路题

一共走n+m布

从中选n布为上

直接C(n+m,n)就可以辣

第一次用逆元求组合数，激动！！！

#include<cstdio> #include<cstring> const int mod=1e9+7,N=1e5+10; long long int aa[2*N]; int gcd(int a,int b,int &x,int &y) { if(!b) { x=1,y=0; return a; } int d=gcd(b,a%b,y,x);y-=x*(a/b); return d; } int main() { int n,m; scanf("%d %d",&n,&m); if(n<0||m<0) { printf("0\n"); return 0; } aa[1]=1; for(int i=2;i<=n+m;i++) aa[i]=aa[i-1]*i%mod; int x,y; long long ans=aa[n+m]; gcd(aa[n],mod,x,y); ans=ans*x%mod; gcd(aa[m],mod,x,y); ans=ans*x%mod; printf("%lld\n",(ans+mod)%mod); return 0; }