链接

试题链接
解题报告备份链接

解题思路

首先，根据杨辉三角形，可知

所以， 可以弄成 来算，这样子就快多了。

然后，我们注意到组合数公式：

再看排列数公式：

例如，

对比以上两个式子，发现了什么问题呢？

对，组合数公式实际上是可以化简分步进行的。

例如，

这个计算可以循环，也就是

1. result 赋值为1
2. 第一轮循环，result 乘上
3. 第二轮循环，result 乘上
4. 第三轮循环，result 乘上
5. 第四轮循环，result 乘上

那么现在，应该知道怎么编写 的算法了。

           +-------+
           |  开始  |
           +-------+
               |
               |
               v
           +----------+
           | 输入m与n  |
           +----------+
                |
                |
                |
                v
                XX
              XXXXXX
           XXXX    XXXXX
        XXXX            XXX      否
     XX    判断n > m / 2     XX--------------------+
      XX                 XXX                       |
         XXX           XXX                         |
           XXXX     XXXX                           |
               XXXXXX                              |
                 XX                                |
                 +                                 |
                 |   是                            |
                 |                                 |
                 v                                 |
          +-------------+                          |
          |  n = m + n  |                          |
          +-------------+                          |
                 |                                 |
                 |                                 |
                 |<--------------------------------+
                 |
                 v        
         +--------------+ 
         |  result = 1  |
         |    i = 1     |
         +-------+------+ 
                 |
                 | <---------------------------------------------+
                 |                                               |
                 v                                               |
    +------------+-------------+                       +---------+----------+
    |   result *= (m+i+1)/i    |                       |         ++i        |
    +-------------+------------+                       +--------------------+
                  |                                                ^
                  |                                                |
                  |                                                |
                  v                                                |    是
                XX                                                X
            XXXX  XXXXXX                                        XX XXXX
         XXX            XXXX       否                         XX       XXXX
      XX                     X                             XXX           XXX
XXXX X  判断result > 10^18    X X                        XXX                XXX
 XXXXX                      XX+---------------------->XXX      i <= n          XX
      XXXX                XXX                         XXXXXX               XXXX
          XXXX         XXX                                 XXXXX         XXX
              X  XX   XX                                        XXXX XXXX
                   XX                                               XX
                   +                                                 +
                   |                                                 |
                   |    是                                            |  否
                   |                                                 |
                   |                                                 |
                   v                                                 v
      +------------+-------------+                       +---------------------------+
      |       输出10^18          |                       |       输出result          |
      +------------+-------------+                       +-------------+-------------+
                   |                                                   |
                   |                                                   |
                   |                                                   |
                   |<--------------------------------------------------+
                   |
                   |
                   v
            +-----------------+
            |      结束       |
            +-----------------+

源代码

#include <cstdio>

const long long upper_limit = 1000000000000000000LL;

long long C(long long m, long long n)
{
    if (n == 0 || n == m)
        return 1;
    if (n > m / 2)
        n = m - n;
    __int128 res = (__int128)1;
    for (long long i = 1; i <= n; ++i)
    {
        res = res * (m-i+1) / i;
        if (res > upper_limit)
            return upper_limit;
    }
    return (long long)res;
}

int main()
{
    long long n, k;
    while (scanf("%lld%lld", &n, &k) != EOF)
    {
        printf("%lld\n", C(n, k));
    }
    return 0;
}