Project_Euler-15 题解

题目

思路

一眼背包问题，再看一眼广度优先搜索，再看一眼排列组合，这里讲一讲排列组合的解法吧：

以$2\ast 2$的组合为例可以发现：

• 无论哪一种方法，从左上角到右下角总共需要四步
• 无论哪一种方法，向右和向下各需要两部

设：

$$\begin{gathered} D=向下走 \\ R=直着走 \end{gathered}$$

我们有如下的可能：

$$ANS=COUNT(DDRR,DRDR,RRDD,RDRD,RDDR,DRRD)=6$$

在四个位置上分配随机选两个位置放D，剩下的R就确定了，因此就是一个排列组合：

$$C{}_4^2=6$$

因此，对于$20\ast 20$的方格，我们需要求：

$$C{}_{40}^{20}$$

代码

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<time.h>

int main(){
    long long m = 40, n = 20, ans = 1;
    while (n > 1) {
        if (m > 20) ans *= (m--);
        if (n && ans % n == 0) ans /= (n--);
    }
    printf("%lld\n", ans);
    return 0;
}