2025-11-22

T1

注意到相同做法的题目，考虑对深度势能法。

T2

注意到可以从大到小贪心，维护 \(nd\)，\(cnt_p\)，表示构造出当前答案的需求量，\(p\) 在前缀中的出现数量。

• 对于 \(cnt_p < nd\)，则 \(nd = nd - cnt_p\)。

• 对于 \(nd \leq nd\)，则 \(cnt_0 = cnt_0 - cnt_p + nd\)。

注意到这个过程可以线段树维护。

T3

未看。

T4

求：

\[\sum_{x=0}^{V} \sum_{i=1}^{n} \sum_{j=i+1}^{m} [\gcd(a_1, a_2, \ldots, a_i, a_j, a_{j+1}, \ldots, a_n)^k \oplus x] \times (a_i + a_j)) \mod 998244353 \]

注意到在前缀/后缀中不同的 \(gcd\) 最多只有 \(\log n\) 种，考虑枚举，算区间贡献。