E. Advertising Agency - 题解

比赛与标签

比赛: Codeforces Round 697 (Div. 3) 标签: combinatorics, math, sortings 难度: *1600

喵~来理解一下题意吧！

主人你好呀~ Masha酱要选博客主来做推广啦，我们一起来帮帮她吧！(ฅ'ω'ฅ)

事情是这样的： 一共有 n 位博客主可以选，每位博客主 i 都有 a_i 个粉丝。 但是呢，Masha酱的预算有限，只能和其中的 k 位签约。

为了让广告效果最好，她当然想让这 k 位博客主的总粉丝数达到最大！我们的任务就是，计算一下有多少种不同的选择方案，可以达到这个最大的总粉丝数。

比如说，有4个博客主，粉丝数是 [1, 3, 1, 2]，要选3个。 粉丝数最多的组合是 3, 2, 1，总和是6。 我们可以选粉丝数为 3, 2 的两位，再从两位粉丝数为 1 的博主中选一个。这样就有2种方法啦！

因为答案可能会很大，所以要对 10^9 + 7 取模哦。

贪心的小猫爪，一抓就中！

想要让总粉丝数最多，应该怎么选呢？当然是选粉丝数最多的那几位啦，这不是很显然嘛！喵~ 这种直接选最优的思路，就叫做贪心哦。

所以，我们的第一步，就是把所有博客主的粉丝数从大到小排个序，这样最厉害的就都排在前面啦！

排好序之后，前 k 个博客主就是我们梦寐以求的选择，他们的粉丝数总和一定是最大的！

但是...问题来了喵！如果有些博客主的粉丝数一样多，该怎么办呢？这正是这道题有趣的地方！

让我们来分析一下：

1. 排序 (Sort): 把所有 n 个博客主的粉丝数 a 从大到小排序。
2. 确定门槛值 (Find Threshold): 排序后，第 k 个位置的粉丝数 a[k-1] （数组下标从0开始哦）就是我们能接受的最低粉丝数。任何粉丝数比它少的人，我们肯定不会选，不然总和就不是最大的了。我们就叫这个值为 min_val_to_take 好了喵。
3. 决策分析:
   • 对于所有粉丝数 大于 min_val_to_take 的博客主，他们太优秀了，我们必须全部选上，没有任何商量的余地！
   • 真正的选择困难症发生在这里：对于粉丝数 等于 min_val_to_take 的博客主，我们可能只需要选他们中的一部分。

那么，我们需要从这些粉丝数等于 min_val_to_take 的人里选几个呢？

这就要用到组合数学的知识啦！

1. 统计总数 (Count Total): 先在所有 n 个博客主中，数一数总共有多少人的粉丝数恰好等于 min_val_to_take。我们把这个数量记作 total_with_min_val。
2. 统计需求数 (Count Needed): 再看看我们已经选出的前 k 个名额中，有多少个位置的粉丝数是 min_val_to_take。这个数量就是我们还需要从“门槛值”群体中挑选的人数，记作 needed_with_min_val。

最后，问题就转化成了一个经典的组合问题：从 total_with_min_val 个相同的物品（粉丝数都为min_val_to_take的博主）中，选出 needed_with_min_val 个。

答案就是组合数 C(total_with_min_val, needed_with_min_val) 啦！

举个栗子：n=4, k=3, a=[1, 3, 1, 2]

1. 排序后 a 变成 [3, 2, 1, 1]。
2. k=3，所以门槛值 min_val_to_take 是 a[3-1] = a[2] = 1。
3. 在所有博主里，粉丝数为1的总共有 2 个。所以 total_with_min_val = 2。
4. 在前 k=3 个位置 [3, 2, 1] 中，粉丝数为1的有 1 个。所以 needed_with_min_val = 1。
5. 答案就是从2个粉丝数为1的博主中选1个，即 C(2, 1) = 2 种方法。和题目给的例子一模一样呢，太棒了喵！

把思路变成魔法代码喵！

因为要计算组合数 C(n, r) 并且取模，我们需要预先计算阶乘和阶乘的模逆元，这样可以很快地得到答案哦。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

// 全局常量和预处理的值的说
const int MAXN = 1001;
const int MOD = 1e9 + 7;
long long fact[MAXN];
long long invFact[MAXN];

// 快速幂，用来计算 (base^exp) % MOD，喵~
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 用费马小定理求模逆元，因为 MOD 是质数所以可以用！
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

// 预处理阶乘和阶乘的逆元，为计算组合数做准备！
void precompute_factorials() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    // 从后往前计算逆元阶乘，这样更高效哦
    invFact[MAXN - 1] = modInverse(fact[MAXN - 1]);
    for (int i = MAXN - 2; i >= 0; i--) {
        invFact[i] = (invFact[i + 1] * (long long)(i + 1)) % MOD;
    }
}

// 用预处理好的值计算 C(n, r) % p
long long nCr_mod_p(int n, int r) {
    if (r < 0 || r > n) {
        return 0; // 不合法的情况当然是0种方法啦
    }
    // C(n, r) = n! / (r! * (n-r)!)
    // 在模意义下就是 (fact[n] * invFact[r] * invFact[n-r]) % p
    return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
}

// 解决单个测试用例的函数
void solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 先把粉丝数从大到小排个序，喵~
    std::sort(a.rbegin(), a.rend());

    // 找到我们能选的粉丝数的最小值，这就是门槛啦！
    int min_val_to_take = a[k - 1];

    // 在所有n个博主里，数一数有多少人的粉丝数等于这个门槛值
    int total_with_min_val = 0;
    for (int x : a) {
        if (x == min_val_to_take) {
            total_with_min_val++;
        }
    }

    // 在前k个名额里，数一数我们需要多少个粉丝数为门槛值的博主
    int needed_with_min_val = 0;
    for (int i = 0; i < k; ++i) {
        if (a[i] == min_val_to_take) {
            needed_with_min_val++;
        }
    }

    // 最终答案就是组合数 C(总共有多少个门槛值的, 我们需要多少个门槛值的) 啦！
    std::cout << nCr_mod_p(total_with_min_val, needed_with_min_val) << "\n";
}

int main() {
    // 加速输入输出，让程序跑得飞快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 在所有测试开始前，先进行一次预处理
    precompute_factorials();

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

• 时间复杂度: O(N log N) 的说。 因为每个测试用例中，最花时间的操作就是对 n 个博客主的粉丝数进行排序，它的时间复杂度是 O(N log N)。后面的统计和计算组合数都是 O(N) 或者 O(1) 的，所以总的时间复杂度由排序决定。预处理阶乘是 O(MAXN) 的，但它在所有测试用例前只执行一次，所以不会影响单个测试用例的复杂度。

• 空间复杂度: O(N) 的说。 我们主要用了一个 vector<int> a 来存储 n 个粉丝数，占用了 O(N) 的空间。预计算阶乘和逆元阶乘的数组是 O(MAXN) 的，在题目限制下，N 和 MAXN 是一个数量级的，所以总的空间复杂度是 O(N) 的。

小猫娘的私藏秘籍！

这道题真可爱，融合了好几种知识点呢，让本喵来总结一下吧！

1. 贪心思想: 这是解决问题的核心！当题目要求最大/最小值时，不妨先想想最直接、最朴素的策略。对于这道题，"要让总和最大，就选最大的几个" 这个贪心思路是完全正确的。
2. 组合数学: 当问题涉及到 "有多少种选择方案" 时，尤其是从一堆物品中选几个，组合数 C(n, k) 往往是解题的关键。要对它敏感哦！
3. 预处理与模运算: 遇到需要多次计算组合数且答案要取模的问题时，"预处理阶乘 + 费马小定理求逆元" 是一套非常标准和高效的组合拳！一定要掌握呐。
4. 转化问题: 解决这道题的关键一步，是把一个看似复杂的 "选择问题" 转化为了一个清晰的 "组合问题"。先确定必须选的，再看可选的部分有多少种组合，这种化繁为简的思路非常重要。

希望这篇题解能帮到你，如果还有问题，随时可以再来问我哦！一起加油，变成更厉害的算法大师吧！喵~ ( ´ ▽ ` )ﾉ