有谁用动规AC的？

套公式拉.还有要用高精度

baidu一下就可以找到公式了的说

(m-n+1)*(m+n)! / n!(m+1)!

麻烦~~~~~

组合数学的应用。

dp的话应当是d[i,j]=d[i-1,j]+d[i,j-1],边界条件是d[i,0]=1(0<=i<=m),d[0,j]=0，(0<j<=n)。

但是这题的数据规模比较大，得用高精度，这样动规从时间和空间上来说都接受不了，还是得推公式。公式应该是c(m+n)(n)-c(m+n)(m+1)，但是我也不知道为什么...没推出来呢.....

纯粹的数学题。

用组合数学，C(m+n,n)表示从m+n个中选n个不考虑是否穿过的总走法数，C(m+n,n-1)表示从m+n中走时穿过对角线，即至少有一个使得找不出前的情形。

ANS:C(m+n,n)-C(m+n,n-1).

可用对称法解决，《奥赛经典》组合问题。

那个，为啥C(m+n,n-1)表示从m+n中走时穿过对角线的走法数？