Description

Problem Link
给定 \(n \times m\) 的长方形，左上角的最大等腰直角三角形不可走，其他地方的点可走，并且只能向上向右走，求有多少种方式能从 \((0,0)\) 到达 \((n,m)\)

Solution

emm … 这个是 Catalan Number 的变式吧，可以推出答案为

\[C^{n+m}^n-C_{n+m}^{n-1} \]

然后输出就可以。

因为答案较大，所以需要高精，懒的搞高精直接上 python 吧！

Code

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));