利用杨辉三角求组合数

求组合数（也就是c几几）的时候我们可以用杨辉三角来进行递推。

介绍

如下图，我们可以看到，第n行第m列就是cnm，但是我们要将第0行第0列先初始化为1，因为我们从第一行开始递推，第一行要用到第0行的数据。注意杨辉三角是从第0行开始的。
如果不会构建杨辉三角可以看这篇

递推公式

c[i][j] = c[i - 1][j - 1] + c[i - 1][j]

源码

#include <iostream>
using namespace std;

const int N = 110;

int c[N][N];

int main()
{
    c[0][0] = 1;
    for (int i = 1; i <= 10; i ++ )
    {
        for (int j = 0; j <= i; j ++ )
        {
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    } 
}

源码最终版

这里的mod是为了防止过大，而爆内存。
这里其实也是利用的杨辉三角，只是它把第第一列都初始化为1了。

void init()
{
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j <= i; j ++ )
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}