社区讨论

萌新刚学 OI,我的常数为什么那么大?

P14636[NOIP2025] 清仓甩卖参与者 5已保存回复 11

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@misz9euo
此快照首次捕获于
2025/12/05 22:46
2 个月前
此快照最后确认于
2025/12/09 03:01
2 个月前
查看原帖
O(n2)O(n^2) 做法,感觉很简洁了。
考场上的代码已经 T 飞了,之后卡了半天常还是跑不过。
这是官方数据,在洛谷上测试了一下,sale24 跑了 2.32s。https://www.luogu.com.cn/record/251583901
至于我的花式 define int long long,是因为我试图使用不同类型来参与计算,但是发现全都变成 long long 之后效率还会变快。
CPP
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = long long;
#define unsigned long long
#define MAXN 5002
#define mod 998244353
unsigned T, n, m, a[MAXN], pow2[MAXN], pp2[MAXN];
unsigned fac[MAXN], inv[MAXN];
inline unsigned qpow(ull x, unsigned y) {
	ull res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
#define C(n, k) ((ull)fac[n] * inv[k] % mod * inv[(n) - (k)] % mod)
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	pow2[0] = pp2[0] = 1;
	for (unsigned i = 1; i <= 5000; i++) {
		pow2[i] = pow2[i - 1] << 1;
		if (pow2[i] >= mod) {
			pow2[i] -= mod;
		}
		pp2[i] = pp2[i - 1] + pow2[i];
		if (pp2[i] >= mod) {
			pp2[i] -= mod;
		}
	}
	fac[0] = 1;
	for (unsigned i = 1; i <= 5000; i++) {
		fac[i] = (ull)fac[i - 1] * i % mod;
	}
	inv[5000] = qpow(fac[5000], mod - 2);
	for (int i = 4999; i >= 0; i--) {
		inv[i] = (ull)inv[i + 1] * (i + 1) % mod;
	}
	cin >> T >> T;
	while (T--) {
		cin >> n >> m;
		__uint128_t ans = 0;
		for (unsigned i = 1; i <= n; i++) {
			cin >> a[i];
		}
		sort(a + 1, a + n + 1, greater<unsigned>());
		for (unsigned i = 1; i < n; ++i) {
			if (m <= i) {
				break;
			}
			for (unsigned j = max<unsigned>(i + 1, m - i + 1); j <= n; ++j) {
				unsigned kkk = n + 1, tmp = a[i] - a[j];
				if (a[i] < (a[j] << 1)) {
					while (a[--kkk] < tmp);
					ans += C(j - 2, m - i - 1) * (pp2[(signed)(n - ++kkk)] + 1);
					if (a[i] == a[j]) {
						ans -= C(j - 2, m - i - 1);
					}
				} else {
					break;
				}
			}
		}
		cout << (pow2[n] - (unsigned)(ans % mod) + mod) % mod << '\n';
	}
	cerr << clock() << ' ' << CLOCKS_PER_SEC << '\n';
	return 0;
}

回复

11 条回复,欢迎继续交流。

正在加载回复...