组合数学相关

ACM模版

定理

One

{1, 2, … n}的r组合a1, a2, … ar出现在所有r组合中的字典序位置编号, C(n, m)表示n中取m的组合数
index = C(n, r) - C(n - a1, r) - C(n - a2, r - 1) - … - C(n - ar, 1)

Two

k * C(n, k) = n * C(n - 1, k - 1);
C(n, 0) + C(n, 2) + … = C(n, 1) + C(n, 3) + …
1 * C(n, 1) + 2 * C(n, 2) + … + n * C(n, n) = n * 2^(n - 1)

Three · Catalan数

C_n = C(2 * n, n) / (n + 1)
C_n = (4 * n - 2) / (n + 1) * C_n - 1
C_1 = 1

Four · Stirling数 · 1

s(p, k)是将p个物体排成k个非空的循环排列的方法数(或者: 把p个人排成k个非空圆圈的方法数)。
s(p, k) = (p - 1) * s(p - 1, k) + s(p - 1, k - 1);

Five · Stirling数 · 2

S(p, k) = k * S(p - 1, k) + S(p - 1, k - 1).
S(p, 0) = 0, (p >= 1);
S(p, p) = 1, (p >= 0);
且有 S(p, 1) = 1, (p >= 1);
S(p, 2) = 2^(p - 1) - 1, (p >= 2);
S(p, p - 1) = C(p, 2);

Six · Bell数

B_p = S(p, 0) + S(p, 1) + … + S(p, p)
B_p = C(p - 1, 0) * B_0 + C(p - 1, 1) * B_1 + … + C(p - 1, p - 1) * B_(p - 1)

应用示例

组合数C(n, r)

int com(int n, int r)   // return C(n, r)
{
    if (n - r > r)
    {
        r = n - r;      // C(n, r) = C(n, n - r)
    }
    int i, j, s = 1;
    for (i = 0, j = 1; i < r; ++i)
    {
        s *= (n - i);
        for (; j <= r && s % j == 0; ++j)
        {
            s /= j;
        }
    }
    return s;
}

组合数C(a, b) (预处理)

typedef long long ll;

const ll MOD = 1e9 + 7;     // 必须为质数才管用
const ll MAXN = 1e5 + 3;

ll fac[MAXN];       // 阶乘
ll inv[MAXN];       // 阶乘的逆元

ll QPow(ll x, ll n)
{
    ll ret = 1;
    ll tmp = x % MOD;

    while (n)
    {
        if (n & 1)
        {
            ret = (ret * tmp) % MOD;
        }
        tmp = tmp * tmp % MOD;
        n >>= 1;
    }

    return ret;
}

void init()
{
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
    }
    inv[MAXN - 1] = QPow(fac[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % MOD;
    }
}

ll C(ll a, ll b)
{
    if (b > a)
    {
        return 0;
    }
    if (b == 0)
    {
        return 1;
    }
    return fac[a] * inv[b] % MOD * inv[a - b] % MOD;
}

                                PS:2016.12.14添加

集合划分问题

/* * n元集合分划为k类的方案数记为S(n, k),称为第二类Stirling数。 * 如{A,B,C}可以划分{
   {A}, {B}, {C}}, {
   {A, B}, {C}}, {
   {B, C}, {A}}, {
   {A, C}, {B}}, {
   {A, B, C}}。 * 即一个集合可以划分为不同集合(1...n个)的种类数 * CALL: compute(N); 每当输入一个n,输出B[n] */
const int N = 2001;
int data[N][N], B[N];

void NGetM(int m, int n)    // m 个数 n 个集合
{
    // data[i][j]: i个数分成j个集合
    int min, i, j;
    data[0][0] = 1;
    for (i = 1; i <= m; i++)
    {
        data[i][0] = 0;
    }
    for (i = 0; i <= m; i++)
    {
        data[i][i + 1] = 0;
    }
    for (i = 1; i <= m; i++)
    {
        if (i < n)
        {
            min = i;
        }
        else
        {
            min = n;
        }
        for (j = 1; j <= min; j++)
        {
                data[i][j] = (j * data[i - 1][j] + data[i - 1][j - 1]);
        }
    }
    return ;
}

void compute(int m)
{
    // b[i]: Bell数
    NGetM(m, m);
    memset(B, 0, sizeof(B));
    int i, j;
    for (i=1; i <= m; i++)
    {
        for (j = 0; j <= i; j++)
        {
            B[i] += data[i][j];
        }
    }
    return ;
}

卢卡斯定理（从(1, 1)到(n, m)的走法，机器人走方格问题）

#define MOD 1000000007
typedef long long LL;

LL quickPower(LL a, LL b)
{
    LL ans = 1;
    a %= MOD;
    while (b)
    {
        if (b & 1)
        {
            ans = ans * a % MOD;
        }
        b >>= 1;
        a = a * a % MOD;
    }
    return ans;
}

LL c(LL n, LL m)
{
    if (m > n)
    {
        return 0;
    }
    LL ans = 1;
    for (int i = 1; i <= m; i++)
    {
        LL a = (n + i - m) % MOD;
        LL b = i % MOD;
        ans = ans * (a * quickPower(b, MOD - 2) % MOD) % MOD;
    }
    return ans;
}

LL lucas(LL n, LL m)
{
    if (m == 0)
    {
        return 1;
    }
    return c(n % MOD, m % MOD) * lucas(n / MOD, m / MOD) % MOD;
}

int main(int argc, const char * argv[])
{
    LL n, m;
    while (~scanf("%lld %lld", &n, &m))
    {
        LL max, min;
        max = n + m - 3;
        min = m - 1;
        printf("%lld\n", lucas(max - 1, min - 1));
    }
    return 0;
}