#P1942. Paths on a Grid

Paths on a Grid

题目描述:

想象你正在上数学课。你又感到无聊了,因为老师在讲你几年前就掌握的内容(这次他在解释 ((a+b)2=a2+2ab+b2)((a+b)^2 = a^2 + 2ab + b^2))。于是你决定把时间花在画 “现代艺术” 上。幸运的是你有一张方格纸,你在纸上选了一个 n×m 大小的矩形。我们把这个矩形及其内部的线条统称为 “网格”。从网格的左下角开始,你移动铅笔到右上角,确保铅笔始终沿着线条移动,且只能向右或向上走。结果如左图所示:

真是一幅杰作,不是吗?再重复一次这个过程,你就会得到右图所示的图案。现在你想知道:你能创作出多少种不同的艺术作品?

输入:

输入包含多个测试用例,每个用例由两个无符号 3232 位整数 nnmm 指定,表示矩形的大小。如你所见,相应网格的线条数在每个维度上均比其大小多 11。输入以 n=m=0n=m=0 终止。

输出:

对于每个测试用例,在一行上输出通过上述过程可生成的不同艺术作品的数量。也就是说,在一个网格中,路径的每一步由向右移动一个单位或向上移动一个单位组成,这样的路径有多少条?你可以放心假设该数量能容纳在 3232 位无符号整数中。

输入数据1

5 4
1 1
0 0

输出数据1

126
2

来源:

乌尔姆当地 2002 年