问从(0,0)出发每一步可以向上走或者向右走,走到(n,m)的方案数有多少种?
两个用空格隔开的整数n和m (mod 1e9+7)。
一个整数,表示方案数。
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; }