自动搬运

查看原文

来自洛谷，原作者为

	Aliemo Caring for everyone, trusting a few people, not betraying anyone, only loving one person

搬运于2025-08-24 21:59:27，当前版本为作者最后更新于2020-08-25 09:09:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接: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);
}