组合数与第二类斯特林数

求解组合数 C（n，m）

暂时有三种方法：

1.存在数组里递归求解

2.较为生猛地求解（连乘连除）

3.改良版（乘一次除一次）

Code(存于数组)

long long c[105][105];
void combine_init()
{
    memset(c, 0, sizeof(c));
    c[0][0] = 1;
    for(int i = 1; i <= 105; ++i)
    {
        c[i][0] = c[i][i] = 1;
        c[i][1] = i;
        for(int j = 1; j < i; ++j)
            if(c[i][j] == 0)
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]);/// % mod
    }
}

Code（连乘连除）

long long violent_combine(long long n,long long m)
{
    if(m < n - m)
        m = n - m;///取个较大值
    long long ans = 1;
    for(long long i = m + 1; i <= n; ++i)/// fac(n) / fac(m)
        ans *= i;
    for(long long i = 1; i <= n - m; ++i)/// fac(n - m)
        ans /= i;
    return ans;
}

Code(乘除共进)

long long combine(long long a, long long b)
{
    if(b > a - b)
        b = a - b;///取个较小值
    long long ans = 1;
    for(int i = 1; i <= b; ++i)
    {
        ans *= (a + 1 - i);/// fac(a) / fac(a - b)
        ans /= i;          /// fac(b)
    }
    return ans;
}

update 第二类斯特林数

c[n][m]把n个元素分到m个非空且不可区分的集合中去

memset(c, 0, sizeof(c));
    c[1][1] = 1;
    for(int i = 2; i<= 105; ++i)
        for(int j = 1; j <= i; ++j)
            if(c[i][j] == 0)
                c[i][j] = (c[i - 1][j] * j + c[i - 1][j - 1]) % mod;