专栏文章

题解：P12256 [蓝桥杯 2024 国 Java B] 数据库

kkuaiCreator
P12256题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipj7tx0
此快照首次捕获于
2025/12/03 12:53
3 个月前
此快照最后确认于
2025/12/03 12:53
3 个月前
查看原文

题目大意

给出一串插入和删除序列，可以任意打乱序列，计算使得插入和删除执行完成后的结果相同的方案总数，结果对 109+710^9+7 取模。

解题思路

考虑有 mm 对二元组 [I1,D1][I2,D2]…[Im,Dm][I_1,D_1][I_2,D_2]\dots[I_m,D_m]。问题可以转换为将 mm 对二元组全排列并且保证每一对二元组都存在 IiI_i 一定在 DiD_i 之前出现。答案为： (2×m)!2m\displaystyle\frac{(2\times m)!}{2^m}。即对 2×m2\times m 个元素全排列后去掉每组的 DiD_i 在前，IiI_i 在后的情况总数。
但是还可能存在 pp 种，只有插入的情况。因此总的答案数为 (2×m+p)!2m\displaystyle\frac{(2\times m+p)!}{2^m} 由于 2×m+p=n2\times m+p=n 所以答案是 n!2m\displaystyle\frac{n!}{2^m}。对结果取余 109+710^9+7，需要求逆元。
CPP
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7, N = 1e5 + 5;
long long fpow(long long a, int b, int mod) {
	long long s = 1;
	while (b > 0) {
		if (b & 1) {
			s = (s * a) % mod;
		}
		a = (a * a) % mod;
		b >>= 1;
	}
	return s;
}
int main() {
	int n;
	cin >> n;
	unordered_map<int, int> opCount; 
	for (int i = 0; i < n; i++) {
		string op;
		int id, val;
		cin >> op >> id;
		if (op == "INSERT") 		cin >> val, opCount[id]++;
		else if (op == "DELETE") 	opCount[id]--;
	}
	int m = 0;
	for (auto& [id, cnt] : opCount) 
		if (cnt == 0) m++;  // 统计成对的INSERT和DELETE
	
	long long fact[N] = {0};
	fact[0] = 1;
	for (int i = 1; i <= n; i++) {
		fact[i] = (fact[i - 1] * i) % MOD;
	}

	long long den = fpow(2, m, MOD);
	long long inv = fpow(den, MOD - 2, MOD);

	long long ans = (fact[n] * inv) % MOD;
	cout << ans << endl;

	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...