POJ 1942 Paths on a Grid (组合数学)

POJ 1942 Paths on a Grid (组合数学)

Description

Input

The input contains several testcases. Each is specified by two unsigned 32-bit integers n and m, denoting the size of the rectangle. As you can observe, the number of lines of the corresponding grid is one more in each dimension. Input is terminated by n=m=0.

Output

For each test case output on a line the number of different art works that can be generated using the procedure described above. That is, how many paths are there on a grid where each step of the path consists of moving one unit to the right or one unit up? You may safely assume that this number fits into a 32-bit unsigned integer.

Sample Input

5 41 10 0

Sample Output

1262

题意

如图所示，给出方格的长和宽，问从左下角走到右上角的路线共有多少条。

思路

一道组合数学的问题，从左下角走到右上角一共需要走m+n步，而向右需要走n步，于是总的次数便是 Cnm+n

AC代码

#include#include#include#include#includeusing namespace std;typedef unsigned long long LL;LL C(LL x,LL y) //求组合数C x y{ LL s=1,i,j; for (i = y + 1, j = 1; i <= x; i++, j++) s = s * i / j; return s;}int main(){ LL n, m; while(~scanf("%I64d%I64d",&n,&m)&&(n||m)) printf("%I64d\n",C(n+m,n>m?n:m)); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。