社区讨论
萌新刚学 OI,我的常数为什么那么大?
P14636[NOIP2025] 清仓甩卖参与者 5已保存回复 11
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 11 条
- 当前快照
- 1 份
- 快照标识符
- @misz9euo
- 此快照首次捕获于
- 2025/12/05 22:46 2 个月前
- 此快照最后确认于
- 2025/12/09 03:01 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 条回复,欢迎继续交流。
正在加载回复...