AGC 基本是都写了代码的。大概是因为做起来比较上头。
AGC058
A
从左往右操作即可。
B
不难发现一个位置控制的是一段区间。DP 即可。
怎么模拟赛都出过啊？AGC 也有原题？
C
相邻相同的先缩一下。然后相邻的 \([1, 2]\) 删掉 \(1\)，\([3, 4]\) 删掉 \(4\)，做完之后再缩一遍。
然后考虑相邻的 \([2, 3]\)：
- 如果我们删去 \(2\)，那么可能会再删去一个 \(3\) 或 \(4\)。
- 如果我们删去 \(3\)，那么可能会再删去一个 \(2\) 或 \(1\)。
也就是说 \(c_1 < c_3, c_4 < c_2\)。
手玩一下大概会发现这也是充分的。
D
组 合 意 义 天 地 灭。
设容斥系数是 \(G(x)\)，我们知道
\[ \begin{align*} \frac1{1-G(x)} &= 1 + x + x^2 = \frac{1-x^3}{1-x} \\ G(x) &= \frac{x-x^3}{1-x^3} \end{align*} \]
考虑组合容斥单位，借助三元 GF，那么这个东西就变成了
\[ \frac{x+y+z-3xyz}{1-xyz} \]
组合，就有
\[ \begin{align*} F(x,y,z) &= \frac1{1-\frac{x+y+z-3xyz}{1-xyz}} \\ &= \frac{1-xyz}{1-x-y-z+2xyz} \\ &= \frac1{1-x-y-z} \frac{1-xyz}{1-\frac{-2xyz}{1-x-y-z}} \\ [x^Ay^Bz^C] F(x,y,z) &= [x^A y^B z^C] \sum_{k\ge 0} \frac{(1-xyz)(-2xyz)^k}{(1-x-y-z)^{k+1}} \\ &= \sum_{k\ge 0} (-2)^k \left[\binom{A+B+C-2k}{k, A-k, B-k, C-k} - \binom{A+B+C-2k-3}{k, A-k-1, B-k-1, C-k-1}\right] \\ \end{align*} \]
E
感觉完全做不来这种思维量大的题 /ng
思考如何求 \(f(x)\)。
我们考虑 \(d(y,z) = \operatorname{inv}(z)\)，所以不妨从 \(x\) 开始，通过不断交换逆序对寻找一个 \(z\)。
那么感性理解，就是交换恰好 \(\lfloor\operatorname{inv}(x)/2\rfloor\) 个逆序对得到的最小的排列。
为了方便，下标从以 \(0\) 开始。
维护当前还可用的交换次数 \(s=\lfloor\operatorname{inv}(x)/2\rfloor\)，我们从前往后贪心，每次从 \(x_{0,\dots,s}\) 中取一个最小的放到 \(z\) 的开头，然后更新 \(s\)。
找到最小的 \(k\) 使得 \(A_k > A_{k+1}\)，那么做完 \(k\) 次操作后必然有
- \(x_{s+1} = A_{k+1}\)，且下一次取到它。因此 \(x_{s+i} = A_{k+i}\) \((i\ge 1)\)。
- 同时，要求 \(s\) 不能有变化。所以 \(x_0 = A_k\)。
逆着做，就相当于把 \(A_{0,\dots,k-1}\) 和 \(A_k\) 向后移动若干步得到 \(x\)。且其移动步数为 \(\lfloor\operatorname{inv}(x)/2\rfloor\)，即 \(\operatorname{inv}(A)\) 或 \(\operatorname{inv}(A)-1\)。
然后先将 \(A_{k+1}\) 贪心往后放，再依次考虑 \(A_{0,\dots,k-1}\) 即可。
贺了 xcyle /ng
F
好吧，看来还是得组合意义了。
记 \(P = 998244353\)。
每条边拆点，然后对于每个边点添加 \(P-1\) 个虚点连向它。
问题变为，为每个点均匀随机赋 \([0,1]\) 内的权值，每个边点的权值都大于其邻居的概率。
这是典的。容斥即可。
AGC057
A
第一个观察，可以连边 \(x\) 和 \(\min(10x, x + 10^{\lfloor\log_{10}x\rfloor+1})\)，则答案为连通块的个数。
第二个观察，连通块的个数等于连通块的根的个数。统计没法连边的点数即可。
第三个观察，连边是单调的，二分即可。
B
写个暴力，乱开个范围，就过了！
C
先取逆。
众所周知，逆着建 Trie。
注意到通过 \(\texttt{x -1 x}\) 可以将 \(x \oplus (2^n-1)\) 的链上左右儿子均交换。
并且，如果我们考虑用 Trie 的结点来描述操作，那么操作的顺序是无妨的。
不妨先做链的交换，最后只需做一次异或。
那么我们通过最深的那层非叶结点儿子的顺序可以确定是否操作该链。
写一个 Trie 维护一下实际编号，那么就做完了。
D
以下将非负整系数线性组合简称为线性组合。其余定义类似。
和 \(\to\) 半。
注意到所有 \((x, S-x)\) 中至多选一个。选出 \((S/2, S)\) 中的所有数即可达到此上界，所以是一个确界。
因此，要最大化长度，每个二元组中应该恰好选一个。
考虑如何调整到字典序最小，那就是换一些 \([1,S/2)\) 中的数进来。称它们为低位。
注意到如果我们确定了低位选哪些数，高位就只有至多一种可能性。令低位的数的集合为 \(X\)。
那么，\(X\) 合法当且仅当：
- \(S\) 不能被 \(X\) 表出。
- 若 \(s < S/2\) 能被 \(X\) 表出，则 \(s \in X\)。否则高位中就会存在 \(S-s\)，这是不合法的。
接下来，我们有一个大力的 \(O(S^2)\) 贪心做法，略去不表。
考虑我们选的最小的数为 \(d\)，那么若 \(s \in X\)，则低位所有 \(s+kd\) 都会被选。所以我们对于模 \(d\) 的余数记录最小的 \(s\) 即可。
那么 \(d\) 呢？显然，\(d\) 是最小的不是 \(S\) 约数的正整数。
E
值很小，直接考虑分层。
令 \(\le k\) 的为 \(0\)，\(> k\) 的为 \(1\)。
那么充要条件是每一行的 \(0\) 的个数和每一列的 \(0\) 的个数构成的可重集与 \(B\) 相同。这是关键的。
我们分步考虑每个 \(k\)，只需要对每个 \(k+1\) 算出排布它们相对于 \(\le k\) 的位置的方案数，也就是考虑每次在 \(\le k+1\) 的矩阵中选出一个子矩阵作为 \(\le k\) 的矩阵的方案数。
根据上面的关键结论，合法的矩阵一定是将 \(\le k\) 的 \(01\) 排序后的矩阵的行列置换后得到的。
（可能很抽象）
记 \(r_{k,i}\) 表示第 \(i\) 行 \(\le k\) 的个数。
那么条件是 \[
j \le r_{k,i} \implies q_j \le r_{k+1,p_i}
\]
即 \[ r_{k+1,p_i} \ge \max\{q_1,q_2,\dots,q_{r_{k,i}}\} \]
注意到这两个数组都是非严格减的，也就是，\(p_{i-1}\) 的决策空间总是 \(p_i\) 的超集。这样的排列方案数是很容易计算的：直接 \(\prod[c_i-(n-i)]\) 即可。其中 \(c_i\) 是 \(p_i\) 的可行决策数。
而当我们确认了所有 \(\max\{q_1,q_2,\dots,q_j\}\) 之后，\(q\) 的方案数也是容易计算的。
F
这种操作往往通过几何意义更为直观，观察发现，令 \((B,X,Y) = (B,B-A,C-B)\)，则相当于变换为 \((B+\min(X,Y),\min(X,Y),|X-Y|)\) 或 \((B-\min(X,Y),|X-Y|,\min(X,Y))\)。
注意每次可选的两种变换，其 \(\{X,Y\}\) 是相同的。也就是，在给定步数后，\(\{X,Y\}\) 是唯一确定的。
我们希望每次做选择 \(\pm x\)，问最后得到的不同 \(B\) 的个数。
显然，我们只需要选一个取正号的子集。
不妨设 \(\gcd(X,Y)=1\)，那么我们是对序列 \[ (\underbrace{a_1,\dots,a_1}_{n_1},\underbrace{a_2,\dots,a_2}_{n_2},\dots,\underbrace{a_k,\dots,a_k}_{n_k},1) \]
的每个前缀计算其子集的本质不同和的个数。
我们先观察一些性质：
- \(a_1 > a_2 > \dots > a_k = 1\)。
- \(a_i = n_{i+1} a_{i+1} + a_{i+2}\) \((1 \le i \le k-2)\)。
- \(a_{k-1} = n_k a_k + 1\)。
因此，我们要求若 \(a_{i+1}\) 被全选，且 \(a_{i+2}\) 至少选择一个，则 \(a_i\) 也要被全选。
同时，可以发现这样的方案的和是两两不同的。
从而 DP 即可。