#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
long double sum[1000001];
ll ans, pre[1000001], inv[1000001];
struct node {
    int a, b;
    node(int a = 0, int b = 0): a(a), b(b) {}
    bool operator<(const node &k)const {
        return sum[a] + sum[k.b] + sum[k.a - k.b] < sum[k.a] + sum[b] + sum[a - b];
    }
};
priority_queue <node> q;
const int mod = 1e9 + 7;
ll qpow(ll a, ll b) {
    ll s = 1;

    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1)
            s = s * a % mod;

    return s;
}
int main() {
    scanf("%d%d", &n, &k), pre[0] = inv[0] = 1;

    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] * i % mod, sum[i] = sum[i - 1] + log(i);

    inv[n] = qpow(pre[n], mod - 2);

    for (int i = n; i > 1; i--)
        inv[i - 1] = inv[i] * i % mod;

    for (int i = 0; i <= n; i++)
        q.push(node(n, i));

    while (k) {
        node x = q.top();
        q.pop();
        k--;
        (ans += pre[x.a] * inv[x.b] % mod * inv[x.a - x.b]) %= mod;

        if (x.a - 1 >= x.b)
            q.push(node(x.a - 1, x.b));
    }

    printf("%lld", ans);
    return 0;
}

最大组合数和问题 题解

算法标签

贪心算法、优先队列（大根堆）、组合数预处理、对数比较法、快速幂求逆元

题目分析

核心问题

从所有满足 $0 \leq b \leq a \leq n$ 的不同组合数 $C_a^b$ 中，选择 $k$ 个求和最大。关键约束是 $n$ 可达 $10^6$、$k$ 可达 $10^5$，直接枚举所有组合数并排序会超出时间和空间限制。

组合数核心性质

1. 组合数对称性：$C_a^b = C_a^{a-b}$，无需重复处理对称项。
2. 大小单调性：固定 $a$ 时，$C_a^b$ 在 $b = \lfloor a/2 \rfloor$ 时取得最大值，向两端递减；固定 $b$ 时，$a$ 越大，$C_a^b$ 通常越大（当 $a \geq 2b$ 时）。
3. 溢出风险：直接计算 $C_a^b$（$a$ 达 $10^6$）会超出整数存储范围，需通过对数转换间接比较大小。

贪心策略合理性

要使 $k$ 个组合数和最大，需每次选择当前未选的最大组合数。利用优先队列维护候选组合数，每次弹出最大值并补充下一个可能的大值，确保贪心选择的最优性。

核心思路

1. 对数转换比较大小：将组合数 $C_a^b$ 转换为对数形式 $\log(C_a^b) = \log(a!) - \log(b!) - \log((a-b)!)$，通过比较对数和间接比较组合数大小，避免溢出。
2. 预处理阶乘与逆元：提前计算阶乘 $pre[a] = a! \mod (10^9+7)$ 和逆元 $inv[a] = (a!)^{-1} \mod (10^9+7)$，用于快速计算组合数的模值（$C_a^b = pre[a] \times inv[b] \times inv[a-b] \mod mod$）。
3. 优先队列维护候选：初始将最大 $a$（即 $a=n$）对应的所有 $b$ 作为候选加入大根堆；每次弹出堆顶（当前最大组合数），将其计入答案后，补充候选 $(a-1, b)$（若 $a-1 \geq b$，保证 $b \leq a-1$，且为下一个可能的大组合数）。
4. 贪心选择 $k$ 次：重复弹出堆顶并补充候选，直至选择 $k$ 个组合数，求和后取模输出。

算法步骤

步骤1：预处理阶乘、对数和、逆元

1. 阶乘 $pre$：$pre[0] = 1$，$pre[i] = pre[i-1] \times i \mod mod$（$1 \leq i \leq n$），存储 $i!$ 的模值。
2. 对数和 $sum$：$sum[0] = 0$，$sum[i] = sum[i-1] + \log(i)$（$1 \leq i \leq n$），用于计算 $\log(C_a^b)$。
3. 逆元 $inv$：利用费马小定理（$mod$ 为质数），先求 $inv[n] = qpow(pre[n], mod-2) \mod mod$，再递推 $inv[i-1] = inv[i] \times i \mod mod$（$n \geq i \geq 1$），存储 $(i!)^{-1}$ 的模值。

步骤2：初始化优先队列

将所有 $a=n$、$b \in [0, n]$ 的组合数对应的 $(a, b)$ 加入大根堆。堆的排序依据是 $\log(C_a^b)$ 的大小（通过结构体重载 < 运算符实现）。

步骤3：贪心选择 $k$ 个组合数

1. 循环 $k$ 次：
   • 弹出堆顶元素 $(a, b)$（当前最大组合数）。
   • 计算 $C_a^b$ 的模值，累加到答案 $ans$ 中（$ans = (ans + C_a^b) \mod mod$）。
   • 若 $a-1 \geq b$，将 $(a-1, b)$ 加入堆（下一个可能的大组合数候选）。
2. 循环结束后，输出 $ans$。

代码解析

核心数据结构与函数

1. 结构体 node

• 存储组合数的参数 $(a, b)$，重载 < 运算符用于堆排序。
• 排序逻辑：比较 $\log(C_a^b)$ 和 $\log(C_{k.a}^{k.b})$ 的大小，等价于比较 $sum[a] - sum[b] - sum[a-b]$ 和 $sum[k.a] - sum[k.b] - sum[k.a - k.b]$ 的大小。
• 重载公式推导：$sum[a] + sum[k.b] + sum[k.a - k.b] < sum[k.a] + sum[b] + sum[a - b]$ 等价于 $\log(C_a^b) > \log(C_{k.a}^{k.b})$，确保堆为大根堆。

2. 快速幂 qpow

• 功能：计算 $a^b \mod mod$，用于求阶乘的逆元（费马小定理）。
• 时间复杂度：$O(\log b)$，高效处理大指数运算。

3. 预处理模块

pre[0] = inv[0] = 1;
for (int i = 1; i <= n; i++) {
    pre[i] = pre[i-1] * i % mod;  // 阶乘模运算
    sum[i] = sum[i-1] + log(i);   // 对数和累加
}
inv[n] = qpow(pre[n], mod-2);     // 求n!的逆元
for (int i = n; i > 1; i--) {
    inv[i-1] = inv[i] * i % mod;  // 递推求(i-1)!的逆元
}

• 逆元递推原理：$(i-1)! = (i!) / i$，故 $(i-1)!^{-1} = (i!)^{-1} \times i \mod mod$，避免重复调用快速幂，降低时间复杂度。

4. 优先队列操作

for (int i = 0; i <= n; i++) q.push(node(n, i));  // 初始候选：a=n的所有b
while (k--) {
    node x = q.top(); q.pop();  // 弹出当前最大组合数
    // 计算C(a,b) = a!/(b!*(a-b)!) mod mod
    ans = (ans + pre[x.a] * inv[x.b] % mod * inv[x.a - x.b]) % mod;
    if (x.a - 1 >= x.b) {
        q.push(node(x.a - 1, x.b));  // 补充候选：a-1, b
    }
}

• 初始候选选择：$a=n$ 是最大的可能值，其对应的组合数整体最大，作为初始候选集。
• 候选补充逻辑：弹出 $(a, b)$ 后，补充 $(a-1, b)$，因为 $a$ 减小 1 后，$b$ 不变的组合数是下一个最可能的大值，且不会与已选组合数重复（$a$ 递减，$(a, b)$ 唯一）。

复杂度分析

• 时间复杂度：$O(n + k \log n)$

  • 预处理阶乘、对数和、逆元：$O(n)$（$n \leq 10^6$，可接受）。
  • 优先队列操作：初始入队 $n+1$ 个元素（$O(n \log n)$），后续 $k$ 次弹出和入队（每次入队最多 1 个元素，$O(k \log n)$）。
  • 总复杂度适配 $n \leq 10^6$、$k \leq 10^5$ 的数据范围。

• 空间复杂度：$O(n)$

  • 存储阶乘 $pre$、逆元 $inv$、对数和 $sum$ 各需 $O(n)$ 空间；优先队列最大容量不超过 $n+1$，整体空间可控。

关键注意事项

1. 对数比较的正确性：$\log$ 是单调递增函数，$\log(C1) > \log(C2)$ 等价于 $C1 > C2$，无精度误差（题目保证有解，无需处理相等情况）。
2. 模运算规则：组合数计算时需分步取模，避免中间结果溢出（$pre[x.a] \times inv[x.b]$ 先取模，再乘 $inv[x.a - x.b]$ 后取模）。
3. 组合数唯一性：每个 $(a, b)$ 对应唯一组合数，优先队列中不会出现重复元素，确保选择的 $k$ 个组合数均不同。