AtCoder Grand Contest 038 题解
A - 01 Matrix
题意
构造一个 \(H\times W\) 的 01 矩阵，使得：
- 对于每一行，1 的个数和 0 的个数的较小值为 \(A\)；
- 对于每一列，1 的个数和 0 的个数的较小值为 \(B\)。
或输出无解。
\(H,W\le 1000,0\le A\le \frac{W}{2},0\le B\le \frac{H}{2}\)
题解
只要将左上角的 \(B\times A\) 的矩阵和右下角的 \((H-B)\times (W-A)\) 的矩阵置为全 1 矩阵即可。
时间复杂度 \(O(HW)\)。
B - Sorting a Segment
题意
给定一个 \(0\) 到 \(N-1\) 的排列 \(P_0,P_1,\ldots,P_{N-1}\)。你需要求有多少本质不同的排列可以通过 \(P\) 通过恰好一次以下操作得到：
- 选择一个长度为 \(K\) 的区间，将该区间中的元素从小到大排序。
\(N\le 2\times 10^5\)
题解
考虑如何判断选择 \([i,i+k-1]\) 和选择 \([j,j+k-1]\) 得到的排列是否相同。
假设有 \(i<j\)。先考虑两个区间有交的情况。此时充要条件是 \([i,j-1]\) 和 \([i+k,j+k-1]\) 分别有序，且 \([i,j-1]\) 中的元素小于相交部分的元素，\([i+k,j+k-1]\) 中的元素大于相交部分。
而两个区间不交时，充要条件则为两个区间分别有序。
注意到对于区间相交的情况，当 \(j=k+1\ (k>i)\) 时若满足条件，则 \(j=k\) 时一定满足条件。所以我们只需要判断 \(j=i+1\) 的情况，这可以用滑动窗口的方法判断。
判断某个区间是否有序可以通过预处理 \([a_i>a_{i-1}]\) 的前缀和实现。
时间复杂度 \(O(N)\)。
C - LCMs
题意
给定正整数序列 \(a_0,a_1,\ldots,a_{n-1}\)，求 \[\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}\operatorname{lcm}(a_i,a_j)\]
\(n\le 2\times 10^5,a_i\le 10^6\)
题解
令 \(c_j\) 表示 \(a_i=j\) 的 \(i\) 数量，\(m\) 表示最大值，则有 \[ \begin{aligned} \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\operatorname{lcm}(a_i,a_j)&=\sum_{i=1}^{m}\sum_{j=1}^{m}c_ic_j\frac{ij}{\gcd(i,j)}\\ &=\sum_{d=1}^{m}\frac{1}{d}\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}c_{id}c_{jd}\cdot id\cdot jd\cdot [\gcd(i,j)=1]\\ &=\sum_{d=1}^{m}\frac{1}{d}\sum_{k=1}^{\lfloor\frac{m}{d}\rfloor}\mu(k)\left(\sum_{i=1}^{\lfloor\frac{m}{dk}\rfloor}c_{idk}\cdot idk\right)^2 \end{aligned} \]
于是我们可以对于所有 \(1\le w\le m\)，预处理出 \[ \sum_{i=1}^{\lfloor\frac{m}{w}\rfloor} c_{iw}\cdot iw \]
这一部分预处理和最后的计算都是调和级数的复杂度。最后只需要把答案减去 \(i=j\) 的情况再除以 \(2\) 即可。
时间复杂度 \(O(m\log m)\)。
D - Unique Path
题意
你需要判断是否存在 \(N\) 个点 \(M\) 条边的无向简单（无重边，无自环）连通图满足 \(Q\) 个限制，其中第 \(i\) 个限制为：
- 若 \(C_i=0\)，\(A_i\) 到 \(B_i\) 恰好有一条简单路径。
- 若 \(C_i=1\)，\(A_i\) 到 \(B_i\) 有两条及以上不同的简单路径。
\(N\le 10^5,N-1\le M\le \frac{N(N-1)}{2},Q\le 10^5\)
题解
假设已经有一张图，考虑如何判断。
考虑建出圆方树，特别地，对于点数为 \(2\) 的点双，不建立方点，直接连边。于是限制条件想变成了：
- 若 \(C_i=0\)，圆方树上圆点 \(A_i\) 到圆点 \(B_i\) 的简单路径不经过方点。
- 若 \(C_i=1\)，圆方树上圆点 \(A_i\) 到圆点 \(B_i\) 的简单路径经过至少一个方点。
若我们只取出 \(C_i=0\) 的限制，将 \(A_i\) 与 \(B_i\) 连边，则这个图的一个生成森林一定是圆方树的一个子图。
于是我们可以取出该图的任意一个生成森林。若此时存在一个 \(C_i=1\) 的限制，有 \(A_i\) 与 \(B_i\) 连通，那一定无解。
假设当前连通块数为 \(K\)。注意到合法的 \(M\) 一定是一个区间。求上界时，我们一定会使方点尽量少，所以一定是只有一个方点与每个连通块中恰好一个点连边。所以上界为 \(\frac{K(K-1)}{2}+(N-K)\)。
通过以上构造可以得到下界不超过 \(K+(N-K)=N\)。显然，\(M=N-1\) 可行当且仅当不存在 \(C_i=1\) 的限制。
注意需要特判 \(K\le 2\) 的情况。
E - Gachapon
题意
有一个生成器，每次会以 \(\frac{A_i}{S}\) 的概率生成 \(0\le i < N\) 的整数 \(i\)，其中 \(S=\sum_{i=0}^{N-1} A_i\)。
生成器会不断生成数直到满足以下条件：
- 对于每个 \(0\le i < N\)，\(i\) 被生成的次数大于等于 \(B_i\)。
求生成器生成的数的数量的期望，对 \(998244353\) 取模。
\(N\le 400,S\le 400,\sum B_i\le 400\)
题解
考虑 Min-Max 容斥，转化为确定一个集合 \(T\) 后，第一次满足以下条件的期望次数：
- 存在一个 \(i\in T\)，满足 \(i\) 被生成的次数大于等于 \(B_i\)。
根据期望的线性性，第一次满足该条件的期望次数等于所有不满足该条件的状态的概率之和。
一个不满足该条件的状态，将生成的数按生成的顺序排列，一定可以看成一段不在 \(T\) 中的数（可能为空），加上一个在 \(T\) 中的数，再一段不在 \(T\) 中的数，加上一个在 \(T\) 中的数，最后再有一段不在 \(T\) 中的数。
那么所有这样的状态的概率之和就可以表示成每一段的概率之和的乘积。
对于一段不在 \(T\) 中的数，我们不关心这些数具体是什么，我们只需要关心在 \(T\) 中的数具体是什么。记 \(S_T=\sum_{i\in T} A_i\)，那么形如「一段不在 \(T\) 中的数，加上一个在 \(T\) 中的数 \(x\)」的所有状态的概率之和为 \[\sum_{i=0}^{\infty}\left(\frac{S-S_T}{S}\right)^i\frac{A_x}{S}=\frac{S}{S_T}\cdot \frac{A_x}{S}=\frac{A_x}{S_T}\]
假设确定了所有 \(T\) 中的数的出现次数 \(c_i\ (0\le c_i < B_i)\)，那么所有强制以 \(T\) 中元素结尾的状态的概率之和，就是这些段的排列方案数乘上每一段的概率之和的乘积，即为 \[\frac{(\sum c_i)!}{\prod c_i!}\cdot \prod_{i\in T}\left(\frac{A_i}{S_T}\right)^{c_i}\]
而不强制 \(T\) 中元素结尾的状态的概率之和还要再乘上最后「一段不在 \(T\) 中的数」的概率之和，即乘上 \[\sum_{i=0}^{\infty}\left(\frac{S-S_T}{S}\right)^i=\frac{S}{S_T}\]
于是我们就可以 DP 了，只需要在 DP 状态中记录 \(S_T\) 和 \(\sum c_i\) 即可。注意要把容斥系数 \((-1)^{|T|-1}\) 也 DP 进去。
时间复杂度 \(O(S(\sum B_i)^2)\)。
F - Two Permutations
题意
有两个 \(0\) 到 \(N-1\) 的排列 \(P_0,P_1,\ldots,P_{N-1}\)，\(Q_0,Q_1,\ldots,Q_{N-1}\)。
求满足以下条件的两个排列 \(A,B\) 的最大距离：
- 对于所有 \(0\le i < N\)，\(A_i=i\) 或 \(A_i=P_i\)；
- 对于所有 \(0\le i < N\)，\(B_i=i\) 或 \(B_i=Q_i\)。
两个排列 \(A,B\) 的距离定义为 \(A_i\ne B_i\) 的 \(i\) 的数量。
\(N\le 10^5\)
题解
我们可以把问题转化为最小化 \(A_i=B_i\) 的 \(i\) 的数量。
我们先置 \(A_i=i,B_i=i\)，然后相当于对于 \(P,Q\) 的每个置换环，要么不变（即 \(A_i=i\) 或 \(B_i=i\)），要么在 \(A\) 或 \(B\) 的对应位置按环的顺序向前旋转一格（即 \(A_i=P_i\) 或 \(B_i=Q_i\)）。
分若干种情况讨论：
- \(P_i=i,Q_i=i\)，则一定有 \(1\) 的贡献；
- \(P_i=i,Q_i\ne i\)，则此时若 \(i\) 在 \(Q\) 中所在的环没有旋转，即 \(B_i=i\)，那么会产生 \(1\) 的贡献；
- \(P_i\ne i,Q_i=i\)，与上一种情况类似；
- \(P_i\ne i,Q_i\ne i\) 且 \(P_i\ne Q_i\)，此时若 \(i\) 在 \(P\) 和 \(Q\) 中对应的环都没有旋转，则有 \(1\) 的贡献；
- \(P_i\ne i,Q_i\ne i\) 且 \(P_i=Q_i\)，此时若 \(i\) 在 \(P\) 和 \(Q\) 中对应的环都没有旋转或者都旋转了，则有 \(1\) 的贡献。
考虑建立一个最小割模型，将每个环看成一个点，对于排列 \(P\) 的每个环，若在 \(S\) 集合则旋转了，在 \(T\) 集合则不旋转；对于排列 \(Q\) 中的每个环，若在 \(T\) 集合则旋转了，在 \(S\) 集合则不旋转。对于上面的每种情况：
- \(P_i=i,Q_i=i\)，答案直接加 \(1\) 即可；
- \(P_i=i,Q_i\ne i\)，\(i\) 在 \(Q\) 中的环向 \(T\) 连边权为 \(1\) 的边；
- \(P_i\ne i,Q_i=i\)，\(S\) 向 \(i\) 在 \(P\) 中的环连边权为 \(1\) 的边；
- \(P_i\ne i,Q_i\ne i\) 且 \(P_i\ne Q_i\)，\(i\) 在 \(Q\) 中的环向 \(i\) 在 \(P\) 中的环连边权为 \(1\) 的边；
- \(P_i\ne i,Q_i\ne i\) 且 \(P_i=Q_i\)，\(i\) 在 \(Q\) 中的环与 \(i\) 在 \(P\) 中的环双向连边权为 \(1\) 的边。
直接跑 Dinic 即可，由于图是二分图，复杂度可以证明是 \(O(M\sqrt{N})\) 的。由于 \(M=O(N)\)，所以总复杂度为 \(O(N\sqrt{N})\)。
