2023-2024 ICPC, NERC, Northern Eurasia Onsite
G
答案为 \(\sum \min\{pre_i,suf_i\}-a_i\) ，其中 \(pre_i,suf_i\) 表示前缀后缀最大值。发现每次区间加1的时候， \(pre_i,suf_i\) 同样最多也有一段区间加1，于是线段树二分找到这个区间，维护一下贡献即可，为便于处理，我实际上求的是 \(\sum suf_i + \sum \min\{pre_i-suf_i,0\}-\sum a_i\) ，线段树上二分 \(0\) 的位置即可求出该式。
H
考虑每个弱连通块，若无环则做法显然。考虑有环的时候，若存在一个方案，则必存在一个包含所有点的环的方案，我们可以枚举环方案中最后到达的点 \(u\) ，将所有目的地为 \(u\) 的移动先忽略，如果忽略后图无环，则显然有解，否则无解。
J
给定 \(a,b,c\) ，求满足 \(ax+by+cz=N\) 的三元组 \((x,y,z)\) 数量， \(N\le 10^9,a,b,c \le 16\) 。
考虑取 \(x^*=x\bmod c,y^*=y\bmod c\) ，则原式为
\[ (x^*+\hat{x}c)a+(y^*+\hat{y}c)b+cz=N \]
则有
\[ z=\frac{N-x^*a-y^*b}{c}-(\hat{x}a+\hat{y}b) \]
令 \(z^*=\frac{N-x^*a-y^*b}{c}\) ，则 \((x,y,z)=(x^*+\hat{x}c,y^*+\hat{y}c,z^*-(\hat{x}a+\hat{y}b))\) ，其中 \(\hat{x},\hat{y} \ge 0\) ，枚举 \(x^*,y^*\) 后，其等价于求满足 \(\hat{x}a+\hat{y}b \le z^*\) 的 \((\hat{x},\hat{y})\) 数量，用类欧求出即可，总复杂度 \(P(c^2\log N)\) 。
或再进行进一步转化，令 \(p^*=\hat{x}\bmod b\) ，有 \((p^*+\hat{p}b)a+\hat{y}b\le z^*\) 等价于 \(\hat{p}a+\hat{y} \le \frac{z^*-p^*a}{b}\) ，该式可直接求出，总复杂度为 \(O(bc^2)\) 。
另解：
本题即求 \([x^N]\frac{1}{(1-x^a)(1-x^b)(1-x^c)}\) ，有结论 \(f_n=\sum_{i>0}-f_{n-i}\cdot [x^i]P(x)\) ，其中 \(P(x)=(1-x^a)(1-x^b)(1-x^c)\) ，做矩乘即可，本题直接矩乘会T，把非0位存下来做也能过，或者手动矩阵乘法展开一下也能过。