tzl 太强了！真挚的膜拜
lhy 太强了！真挚的膜拜
E. Sets of Complementary Sums
https://codeforces.com/contest/2125/problem/E
分拆数、其实是个不牛的东西，但是写假了 😅
令集合元素升序排列为 \(b_{1\sim n}\)。显然有结论 \(\sum b\geqslant (n-1)(b_n+1)\)，化一下就有 \(b_n\geqslant \left(\sum\limits_{i=1}^{n-1} b_n-b_i\right)+(n-1)\)。发现 RSH 取值对 LSH 无影响（从取等开始，RSH 不变，若 \(b_n\gets b_n+1\)，只需将每个 \(b_i\gets b_i+1\) 即可构造出一组解），故只用考虑 RSH 的每种取值下的方案。
然后就可以做 分拆数 了。发现会 MLE，滚动即可。每次暴力 assign 会很慢，可以用一点巧思清空滚动数组。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int T;
for (std::cin >> T; T--; ) {
long long n, m;
std::cin >> n >> m;
if (n * (n - 1) / 2 > m) {
std::cout << 0 << '\n';
continue;
}
if (n == 1) {
std::cout << m << '\n';
continue;
}
--n;
std::vector<std::vector<long long> > f(2, std::vector <long long> (m + 1));
f[0][0] = 1ll;
for (int j = 1, at = 1; j <= n; ++j, at ^= 1)
for (int i = 0; i <= m; ++i) {
if (i < j)
f[at][i] = 0;
else
f[at][i] = (f[at ^ 1][i - j] + f[at][i - j]) % mod;
}
auto res(0ll);
for (int i = 1; i <= m - n; ++i)
(res += f[n & 1][i] * (m - (i + n) + 1)) %= mod;
std::cout << res << '\n';
}
return 0;
}vp 记录
A
1:43 切。打 std:: 还是太费时间了。
B
5:46 切，看完题没想到 gcd，输出的时候想到了。莼菜。
C
11:23 切，原因是容斥符号乱写。
D
24:21 切，中间重构了一次并且前缀和的部分考虑得有点问题。绅士（38:35）问我为啥做这么快。
E.0
看了一眼感觉不太可做。quack 说 F 板板，故跳。
F
01:13:41 草完。奇怪的 WQS 二分板板。吃了一发罚时，原因是没人合法的时候要输出 \(0\)。但和 maimai 的 30 发比起来还是相形见绌。绅士考虑了这个，但是没判目标 \(<\) 当前的情况遗憾 4 题离场。
场下看了 Diagnostics，发现其实第二发有个地方是 RE 了的（长度不足 \(6\) 我的 *std::max_element 会飞起来），但是不知道为啥就是 A 了。
E.1
猜到结论之后止步于此。试着打了分拆数然后（实际上是）写挂了，怀疑自己结论出错直到 5 题招笑离场 😅
B.1
哈哈 B 的 gcd 没开 long long 被 hack 了，rk55 to 6000+