Paths on a Grid

ACM-ICPC

Publish Date: 2020-01-15

题目大意

给你一个n*m的矩阵，最开始在左上角，只能向下或者向右，求，从左上走到右下的所有路线的方案数。
点击进入原题地址
不难发现，需要走n+m步，然后从n+m中挑出n个走下，即答案就是$C _{m+n}^{m}$

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

思路

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

代码

#include<cstdio>
#include<iostream>
#include<cstring>
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;
}