题解 | #人员分组问题#

题目链接

题目描述

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

解题思路

本题是一个基础的组合计数问题。我们需要计算从 $n$ 个人中选出 $5$ 人、 $6$ 人、 $7$ 人的方案数之和。

问题分解

小组的人数可以是 $5$ 、 $6$ 或 $7$ 人，这三种情况是互斥的。因此，总的组合数量是这三种情况的组合数之和：

\text{Ans} = (C(n, 5) + C(n, 6) + C(n, 7)) \pmod p

其中 $C(n, k)$ 表示从 $n$ 个不同元素中选出 $k$ 个元素的组合数，模数 $p = 1,000,000,007$ 。

组合数计算

由于输入 $n$ 的范围可以达到 $10^6$ ，预计算所有阶乘的方案会占用过大的空间且没有必要。注意到我们需要计算的 $k$ 值非常小（最大为7），我们可以采用一种更直接的计算方法。

组合数的计算公式可以写作：

C(n, k) = \frac{n \cdot (n-1) \cdot \dots \cdot (n-k+1)}{k!} = \left( \prod_{i=0}^{k-1} (n-i) \right) \cdot (k!)^{-1}

在模算术下，这变为：

C(n, k) \pmod p = \left( \left( \prod_{i=0}^{k-1} (n-i) \right) \pmod p \cdot (k!)^{-1} \pmod p \right) \pmod p

分子部分 $\prod_{i=0}^{k-1} (n-i)$ ：可以通过一个 $k$ 次的循环来计算。
分母部分 $(k!)^{-1}$ ：由于 $k$ 很小，我们可以直接计算出 $k!$ ，然后利用费马小定理和快速幂算法求出其关于模 $p$ 的乘法逆元。

算法流程

实现快速幂和逆元函数：编写 power(base, exp) 和 modInverse(num) 函数，用于计算模逆元。
实现组合数函数：编写一个 combinations(n, k) 函数。
- 处理边界情况：如果 $k < 0$ 或 $k > n$ ，组合数为 $0$ 。
- 用循环计算分子的累乘积。
- 用循环计算分母 $k!$ 。
- 计算 $k!$ 的逆元。
- 将分子和分母的逆元相乘，得到最终结果。
主逻辑：读入 $n$ ，分别调用 combinations(n, 5), combinations(n, 6), combinations(n, 7)，将结果相加并取模。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

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

long long modInverse(long long n) {
    long long mod = 1000000007;
    return power(n, mod - 2);
}

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

    long long mod = 1000000007;
    
    long long numerator = 1;
    for (int i = 0; i < k; ++i) {
        numerator = (numerator * (n - i)) % mod;
    }
    
    long long denominator = 1;
    for (int i = 1; i <= k; ++i) {
        denominator = (denominator * i) % mod;
    }
    
    return (numerator * modInverse(denominator)) % mod;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long n;
    cin >> n;
    
    long long mod = 1000000007;
    long long ans = 0;
    ans = (ans + combinations(n, 5)) % mod;
    ans = (ans + combinations(n, 6)) % mod;
    ans = (ans + combinations(n, 7)) % mod;
    
    cout << ans << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    static final int MOD = 1000000007;

    public 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;
    }

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

    public 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 * modInverse(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 = 1000000007

def power(base, exp):
    res = 1
    base %= MOD
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % MOD
        base = (base * base) % MOD
        exp //= 2
    return res

def mod_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 * mod_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)

算法及复杂度

算法：组合数学、费马小定理、快速幂
时间复杂度：combinations(n, k) 函数的复杂度由计算分子和分母的循环以及快速幂决定。循环次数为 $k$ 次，快速幂为 $\mathcal{O}(\log MOD)$ 。由于 $k$ 是一个很小的常数（最大为7），所以单次组合数计算的复杂度可以视为 $\mathcal{O}(\log MOD)$ 。总时间复杂度为 $\mathcal{O}(\log MOD)$ 。
空间复杂度：只使用了常数个变量，空间复杂度为 $\mathcal{O}(1)$ 。