bzoj 3907: 网格 组合数学

3907: 网格

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 13  Solved: 7
[Submit][Status][Discuss]

Description


城市的街道呈网格状,左下角坐标为A(0, 0),右上角坐标为B(n, m),其中n >= m。现在从A(0,
0)点出发,只能沿着街道向正右方或者正上方行走,且不能经过图示中直线左上方的点,即任何途径的点(x, y)都要满足x >=
y,请问在这些前提下,到达B(n, m)有多少种走法。
bzoj 3907: 网格 组合数学

Input

输入文件中仅有一行,包含两个整数n和m,表示城市街区的规模。

Output

输出文件中仅有一个整数和一个换行/回车符,表示不同的方案总数。

Sample Input

6 6

Sample Output

132

HINT

100%的数据中,1 <= m <= n <= 5 000
 
  这道题可以转化成一次BestCoder#32的题目我们以y=x这条线将地图补齐,那么就转化成了对于一串括号“(((?????"求合法方案数,那么结合卡特兰数公式h(n)=C(2n,n)-C(2n,n+1)的推导方法可以很容易拓展到本题,详细公式参见代码,当然上诉思路的括号翻转也可以视为从第一次“越界”后的路径延y=x翻转。
def C(n,m):
return fact[n]/fact[m]/fact[n-m];
f=raw_input().split(" ");
n=int(f[0]);
m=int(f[1]);
tot=max(n,m)*2;
fact=[1];
for i in range(1,tot+1):
fact.append(fact[-1]*i);
c=n-m;
ans=C(tot-c,tot/2)-C(tot-c,tot/2+1);
print ans;
上一篇:Spring Security 之基本概念


下一篇:STM8程序在IAR中报错 unable to allocate space for sections