只能走上和右,且必有n个右,m个上,共n+m步。
把路径写写出就可以发现
如:
样例1:
上上上上右右右右右
…
只要从n+m个里面选出min(n,m)为上或右即可。
利用求组合数的递推公式。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int main()
{
ll n,m;
while(scanf("%lld%lld",&n,&m),n||m)
{
ll ans=1,k=min(n,m),num=n+m;
for(ll i=1;i<=k;i++)
ans=ans*(num-i+1)/i;
printf("%lld\n",ans);
}
return 0;
}