「BZOJ3907」网格
Description
某城市的街道呈网格状，左下角坐标为A(0, 0)，右上角坐标为B(n, m)，其中n >= m。现在从A(0, 0)点出发，只能沿着街道向正右方或者正上方行走，且不能经过图示中直线左上方的点，即任何途径的点(x, y)都要满足x >= y，请问在这些前提下，到达B(n, m)有多少种走法。
.png)
Input
输入文件中仅有一行，包含两个整数n和m，表示城市街区的规模。
Output
输出文件中仅有一个整数和一个换行/回车符，表示不同的方案总数。
Sample Input
6 6
Sample Output
132
HINT
100%的数据中，1 <= m <= n <= 5 000
题解
百度卡特兰数的证明噜。。。
偷懒学python。。。
|
1 2 3 4 5 6 7 8 9 |
fac={}; def C(n,m): return fac[n]/fac[m]/fac[n-m]; fac[0]=1; for i in range(1,10000): fac[i]=fac[i-1]*i; f=raw_input().split(" "); n=int(f[0]);m=int(f[1]); print(C(n+m,n)-C(n+m,n+1)); |
Subscribe
计数器 9786029
OI 课件=>
OI 课件=>