题解 | #人员分组问题#

题目链接

人员分组问题

题目描述

某公司计划从 $n$ 份简历中选拔人员，成立一个恰好由 5 到 7 人组成的创新小组。请计算所有可能的小组组合数量，结果对 $1,000,000,007$ 取模。

输入:

一行输入一个整数 $n$ ，表示应聘者数量。

输出:

输出一个整数，表示所有满足条件的小组组合数量对 $1,000,000,007$ 取模的结果。

解题思路

这个问题可以分解为三个互不相干的子问题，然后将它们的结果相加。根据加法原理，总的方案数等于： (选5人的方案数) + (选6人的方案数) + (选7人的方案数)

从 $n$ 个人中选5人的方案数，即为组合数 $C(n, 5)$ 。
从 $n$ 个人中选6人的方案数，即为组合数 $C(n, 6)$ 。
从 $n$ 个人中选7人的方案数，即为组合数 $C(n, 7)$ 。

因此，总方案数 = $C(n, 5) + C(n, 6) + C(n, 7)$ 。

接下来的关键是如何在模 $P = 1,000,000,007$ 的前提下计算 $C(n, k)$ 。

组合数公式
- $C(n, k) = \frac{n \cdot (n-1) \cdot \dots \cdot (n-k+1)}{k!}$
- 由于 $n$ 的值可能非常大（高达 $10^9$ ），我们不能像之前那样预处理阶乘。但幸运的是， $k$ 的值非常小（最大为7）。
计算 $C(n, k)$ for small k
- 我们可以直接计算公式的分子和分母。
- 分子： $\text{numerator} = \prod_{i=0}^{k-1} (n-i) \pmod P$ 。这可以通过一个简单的循环来计算。
- 分母： $\text{denominator} = k! \pmod P$ 。由于 $k$ 很小，可以直接计算。
- 组合： $C(n, k) \equiv \text{numerator} \cdot (\text{denominator})^{-1} \pmod P$ 。其中 $(\text{denominator})^{-1}$ 是 $k!$ 在模 $P$ 下的 模逆元。
模逆元
- 因为模数 $P=1,000,000,007$ 是一个质数，我们可以使用 费马小定理 求逆元： $x^{-1} \equiv x^{P-2} \pmod P$ 。
- 这个幂次可以用 快速幂 算法高效求出。

算法步骤：

创建一个 combinations(n, k) 函数。
在此函数中，如果 $n < k$ ，直接返回 0。
循环计算分子 $\prod_{i=0}^{k-1} (n-i)$ ，每步取模。
计算分母 $k!$ 。
使用快速幂计算分母的模逆元。
返回 (分子 * 模逆元) % 模数。
主程序调用 combinations(n, 5), combinations(n, 6), combinations(n, 7)，将结果相加并再次取模，然后输出。

代码

cpp
java
python

#include <iostream>

using namespace std;
using LL = long long;

const int MOD = 1e9 + 7;

LL power(LL base, LL exp) {
    LL res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

LL inverse(LL n) {
    return power(n, MOD - 2);
}

LL combinations(LL n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }
    if (k == 0 || k == n) {
        return 1;
    }
    if (k > n / 2) {
        k = n - k;
    }

    LL numerator = 1;
    for (int i = 0; i < k; ++i) {
        numerator = (numerator * (n - i)) % MOD;
    }

    LL denominator = 1;
    for (int i = 1; i <= k; ++i) {
        denominator = (denominator * i) % MOD;
    }

    return (numerator * inverse(denominator)) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    LL n;
    cin >> n;

    LL ans = 0;
    ans = (ans + combinations(n, 5)) % MOD;
    ans = (ans + combinations(n, 6)) % MOD;
    ans = (ans + combinations(n, 7)) % MOD;

    cout << ans << '\n';

    return 0;
}

import java.util.Scanner;

public class Main {
    static final int MOD = 1_000_000_007;

    static long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % MOD;
            }
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    static long inverse(long n) {
        return power(n, MOD - 2);
    }

    static long combinations(long n, int k) {
        if (k < 0 || k > n) {
            return 0;
        }
        if (k == 0 || k == n) {
            return 1;
        }
        if (k > n / 2) {
            k = (int) (n - k);
        }

        long numerator = 1;
        for (int i = 0; i < k; i++) {
            numerator = (numerator * (n - i)) % MOD;
        }

        long denominator = 1;
        for (int i = 1; i <= k; i++) {
            denominator = (denominator * i) % MOD;
        }

        return (numerator * inverse(denominator)) % MOD;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();

        long ans = 0;
        ans = (ans + combinations(n, 5)) % MOD;
        ans = (ans + combinations(n, 6)) % MOD;
        ans = (ans + combinations(n, 7)) % MOD;

        System.out.println(ans);
    }
}

MOD = 1_000_000_007

def power(base, exp):
    return pow(base, exp, MOD)

def inverse(n):
    return power(n, MOD - 2)

def combinations(n, k):
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    if k > n // 2:
        k = n - k
    
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % MOD
    
    denominator = 1
    for i in range(1, k + 1):
        denominator = (denominator * i) % MOD
        
    return (numerator * inverse(denominator)) % MOD

n = int(input())

ans = 0
ans = (ans + combinations(n, 5)) % MOD
ans = (ans + combinations(n, 6)) % MOD
ans = (ans + combinations(n, 7)) % MOD

print(ans)

算法及复杂度

算法：组合数学、加法原理、费马小定理、快速幂
时间复杂度： $\mathcal{O}(k_{max} + \log(\text{MOD}))$ ，其中 $k_{max}=7$ 。对于每个组合数计算，时间主要花费在循环（ $k$ 次）和快速幂上。由于 $k$ 是一个很小的常数，总时间复杂度可视为 $\mathcal{O}(1)$ 。
空间复杂度： $\mathcal{O}(1)$ 。