题解 | 排列组合法 #网格走法数目#

#include <stdio.h>
//由题目知道，在x*y的网格中,我们只能向下x次,和向右y次
//每一次都是一个决策点
//题目简化为在（x+y）步中选择x次向下(或者y次向右)
//也就是排列组合中的组合
int main() {
    int x=0,y=0;
    scanf("%d %d",&x,&y);
    
    long long sum=1;//排列数(用long long 不用 int 是因为数字太大越界了)
    int num=1;//阶乘
    int times = x + y ;//向右和向下的次数和

    for(int i=1;i<=y;i++) 
    {
    sum*=times--;
    num*=i;//算阶乘
    }
   
    printf("%lld\n",sum/num);// 排列数除以阶乘就是组合数
    return 0;
}
//ps:该方法只能算较小的数，大数有可能超出数字范围