2505 上学路线
时间限制: 1 s
空间限制: 64000 KB
题目等级 : 钻石 Diamond
题目描述 Description
因为是学生，所以显然小A每天都要上学。小A所在的城市的道路构成了一个n*m的网格，每条道路都是可以单向通行的。小A家在点(1,1)，学校在点(n,m)。在不移出边界的情况下，小A可以从点(x,y)移动到点(x+1,y)或(x,y+1)。为了追求新鲜感，小A经常走不同的道路去上学。有一天，小A突发奇想：到底他可以有多少种不同的上学路线呢？
输入描述 Input Description
两个正整数n,m,意义如前所述。
输出描述 Output Description
一个正整数，小A的上学路线数量。
样例输入 Sample Input
2 3
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
对于30%的数据，n,m<=100;
对于100%的数据，n+m<=40000.
分类标签 Tags
组合数学 高精度 数论
/*
code没时间打了.
刚听gxh学长讲了一遍.
(之前学数学竞赛的%%%)
理理思路.
这题无论怎么走
若能到达(n,m)点就必定走了n+m-2步.
反过来走n+m-2步一定能走到(n,m)点.
然后我们设向上走为1,向右走为0.
那么问题转化为在长度为n+m-2的序列中放n-1个1 or m-1个0的方案数.
(两个问题显然等价).
恩就是这样.
*/