本文共 983 字，大约阅读时间需要 3 分钟。

题目大意

给你一个n*m的矩阵，最开始在左上角，只能向下或者向右，求，从左上走到右下的所有路线的方案数。

不难发现，需要走n+m步，然后从n+m中挑出n个走下，即答案就是 $C_{m+n}^n$

但是！

本题的询问较多，且差距较大，是无法通过递推得到的。 所以就要利用一种求单个组合数的方法。

思路

$C_n^k$的本质是${\Pi }_{n-k+1}^n$ $÷$ ${\Pi }_1^k$

所以我们把它当成k个 分数 乘起来就好了。（分子分母分别乘可能会爆longlong） 即ans=$\frac{n}{k}\ast \frac{n-1}{k-1}\ast \frac{n-2}{k-2}\ast ...\ast \frac{n-k+1}{1}$ 由于浮点数可能会产生误差，所以最终结果要加上0.5再取整

代码

#include
   
    #include
    
     #include
     
      using namespace std;int n,m;unsigned calc(unsigned n,unsigned m){
       double ans=1.0,a=(double)m+n,b=(double)min(n,m);    while(b){
           ans*=a/b;        a--;b--;    }    ans+=0.5;    return (unsigned)ans;}int main(){
       while(~scanf("%d%d",&n,&m)){
           if(!m&&!n) break;//结束条件        printf("%u\n",calc(n,m));    }    return 0;}
     
    
   

芭芭拉冲鸭！

“人们都在沉醉，人们都已忘却，人们都装作看都这结尾，一味陷入争辩，无人聆听箴言，该可悲可泣或改叹可怜。”–《绝体绝命》（阿良良木健/洛天依）

转载地址：http://luuci.baihongyu.com/