题解 P4370 【[Code+#4]组合数问题2】

· · 题解

题目链接:P4370 [Code+#4]组合数问题2

题目大意

给你两个数 n,k , 要求对于组合数 C_b^a 找到任何 k 个, 让他们的和最大, 且组合数各不相同, 当且仅当 a,b 不完全相同时,组合数不同

solution

规律

我们来观察一下组合数的递推式 : C_n^m = C_{n - 1}^m + C_{n - 1}^{m - 1}

发现, C_n^m > C_{n - 1}^m 那我们可以把所有的 C_n^i 加入优先队列然后弹出的时候加入 C_{n - 1}^i

那为什么不加入 C_{n - 1}^{i - 1} 呢?

我们发现 C_n^m = C_{n - 1}^m + C_{n - 1}^{m - 1} 且 C_n^{m - 1} = C_{n - 1}^{m - 1} + C_{n - 1}^{m - 2}

发现 C_{n - 1}^{i - 1} 会被上一个数使用,但题目要求不能有相同的,所以我们仅仅加入 C_{n - 1}^i 即可.

细节

但是,我们这样做完就会 A 么? 你以为紫题这么简单??

我们会发现优先队列装不下, 数太大了, n = 10^6 诶, 但是取模之后,我们就不知道谁大谁小了/微笑

那我们该怎么办呢?

在高中的时候会学到对数,我们知道,y=logx的函数是单调递增的,那我们可以将所有的组合数取 log 之后放进去.

那我们怎么加入呢?下面,让我们来推导一下这个log的过程

log C_n^m = log \dfrac{n!}{m!(n - m!)} \ \ \ \ \ \ \ \ \ \ \ \ \ = log n! - log m! - log (n - m)! \ \ \ \ \ \ \ \ \ \ \ \ \ = \sum\limits_{i = 1}^{n}log i - \sum\limits_{i = 1}^{m}log i - \sum\limits_{i = 1}^{n - m}log i

我们做一个 log i的前缀和就可以了

我们可以提前预处理出来需要的值,然后在询问的时候直接做就可以了, 总体复杂度 O(n + klogn)

妈妈再也不用担心我没有 A 过紫题了

code:

/**
 *    Author: Alieme
 *    Data: 2020.8.25
 *    Problem: Luogu P4370
 *    Time: O(n + klogn)
 */
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>

#define int long long // 不开longlong 见祖宗
#define rr register

#define inf 1e9
#define MAXN 5000010

using namespace std;

const int mod = 1e9 + 7;

inline int read() {
    int s = 0, f = 0;
    char ch = getchar();
    while (!isdigit(ch)) f |= ch == '-', ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}

void print(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar(x % 10 + 48);
}

struct Node {
    double val; // 记录log
    int x, y; // 记录一下n和i
    Node() {}
    Node(int X, int Y, double VAL) { x = X, y = Y, val = VAL;}
    bool operator < (const Node &b) const { return val < b.val;} // 大根堆
};

int n, k, ans;

int jc[MAXN], inv[MAXN];

double lg[MAXN];

priority_queue<Node> q;  // 优先队列

inline void init() { // 预处理阶乘,逆元,log
    jc[0] = inv[0] = inv[1] = 1;
    for (rr int i = 1; i <= 1000000; i++) jc[i] = i * jc[i - 1] % mod;
    for (rr int i = 2; i <= 1000000; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for (rr int i = 1; i <= 1000000; i++) inv[i] = inv[i] * inv[i - 1] % mod;
    for (rr int i = 1; i <= 1000000; i++) lg[i] = lg[i - 1] + log(i); //有log真好,省的自己写了
}

signed main() {
    init();
    n = read();
    k = read();
    for (rr int i = 0; i <= n; i++) q.push(Node(n, i, lg[n] - lg[i] - lg[n - i])); // 把C加入
    while (k--) {
        Node p = q.top();
        q.pop();
        // cout << p.x << " " << p.y << " " << "\n";
        ans = (ans + jc[p.x] * inv[p.y] % mod * inv[p.x - p.y]) % mod;
        q.push(Node(p.x - 1, p.y, lg[p.x - 1] - lg[p.y] - lg[p.x - 1 - p.y])); // 每次用完之后再加入
    }
    print(ans);
}