AtCoder Grand Contest 046 题解
A - Takahashikun, The Strider
题意
有一个人，初始时在 \((0,0)\)，面向 \(y\) 轴正方向。每一步会向前走一个单位，然后逆时针旋转 \(X^{\circ}\)。
求第一次回到 \((0,0)\) 时用的步数。
题解
可以证明答案为 \(\frac{360}{\gcd(X,360)}\)。
B - Extension
题意
有一个 \(A\times B\) 的全白网格。每次可以在上面加上一行，并且将这一行的恰好一个格子染成黑色；或者在右边加上一列，并且将这一列的恰好一个格子染成黑色。
求通过若干次操作后 \(C\times D\) 的本质不同的网格数量。对 \(998244353\) 取模。
\(C,D\le 3000\)
题解
直接 DP，记 \(f_{i,j}\) 为 \(i\times j\) 的本质不同网格数量。转移考虑最后一次操作是扩充行还是扩充列，但是注意右上角为白色的方案会被算两次，要减去。转移方程为
\[f_{i,j}=f_{i-1,j}\times j+f_{i,j-1}\times i-f_{i-1,j-1}\times (i-1)\times (j-1)\]
时间复杂度 \(O(CD)\)。
C - Shift
题意
给定 01 字符串 \(S\)，求有多少本质不同的字符串可以通过 \(S\) 执行 \(0\) 到 \(K\) 次以下操作得到：
- 选择 \(i,j\ (i<j)\) 满足 \(S_i=0,S_j=1\)，将 \(S_j\) 移动到 \(S_i\) 的左边。
\(|S|\le 300,K\le 10^9\)
题解
考虑将相邻的 \(0\) 之间（包括首尾）\(1\) 的数量依次记为 \(a_1,a_2,\ldots,a_m\)。
则一次操作相当于 \(a_i\gets a_i+1,a_j\gets a_j-1\)，其中 \(i<j\)。
考虑最终得到的序列 \(b_1,b_2,\ldots,b_m\)，需要满足：
- 对于所有 \(1\le i\le m\)，满足 \(\sum\limits_{j=1}^{i} b_j\ge \sum\limits_{j=1}^{i} a_j\)；
- \(\sum\limits_{i=1}^{m}b_i=\sum\limits_{i=1}^{m}a_i\)；
- \(\sum\limits_{i=1}^{m}\max(b_i-a_i,0)\le k\)
于是在 DP 状态中记录当前 \(b_i\) 之和以及 \(\max(b_i-a_i,0)\) 之和，直接转移是 \(O(|S|^4)\) 的，可以用前缀和优化到 \(O(|S|^3)\)。
D - Secret Passage
题意
给定 01 字符串 \(S\)，求有多少本质不同的字符串可以通过 \(S\) 执行若干次（包括 \(0\) 次）以下操作得到：
- 删除前两个字符中的一个，将另一个插入到字符串中的任意位置。
\(|S|\le 300\)
题解
考虑将 \(T\) 表示成 \(S\) 的一个后缀中插入若干个 \(0,1\)。
为了判断 \(T\) 能否通过 \(S\) 得到，我们一定会使这个表示中 \(0,1\) 数量尽量，也就是 \(S\) 的后缀尽量长。
那么我们用 \(f[i][j][k]\) 表示后缀为 \(S[i+1,n]\)，需要插入 \(j\) 个 \(0\)、\(k\) 个 \(1\) 的字符串 \(T\) 的数量。因为我们保证后缀尽量长，所以不会算重。
接下来我们需要考虑的问题是通过删除前缀 \(S[1..i]\)，能否向后缀中插入 \(j\) 个 \(0\) 和 \(k\) 个 \(1\)。
令 \(g[i][j][k]\) 表示已经删除前缀 \(S[1..i]\)，向后缀中插入 \(j\) 个 \(0\) 和 \(k\) 个 \(1\) 时，最多有多少个字符可以被再次删除。
转移考虑直接删除 \(i\) 和 \(i+1\) 还是删除 \(i\) 和之前一个删除后插入到该位置的字符。
最后对于 \(i,j,k\)，若存在一个 \(i'\le i,j'\ge j,k'\ge k\) 满足 \(g[i'][j'][k']\ge 0\)，则答案加上 \(f[i][j][k]\) 即可。
时间复杂度 \(O(|S|^3)\)。
E - Permutation Cover
题意
你需要构造一个满足以下条件的序列 \(P\)，无解输出 \(-1\)：
- 序列中每个元素为 \(1\) 到 \(K\) 的整数，且整数 \(i\) 恰好出现 \(a_i\) 次。
- 对于序列中每个元素，都存在至少一个连续子序列包含该元素并且是一个 \(1\) 到 \(K\) 的排列。
在满足以上条件的前提下要求字典序最小。
\(K\le 100,\sum a_i\le 1000\)
题解
令 \(x=\max a_i,y=\min a_i\)，则有解的充要条件为 \(x\le 2y\)，证明如下：
必要性：假设不满足该条件。取满足 \(a_i=x\) 的任意一个 \(i\) 和满足 \(a_i=y\) 的任意一个 \(j\)，只考虑序列 \(P\) 中值为 \(i\) 或 \(j\) 的位置按相对顺序拿出来组成一个新的序列，则必定存在一个值为 \(i\) 的位置只与 \(i\) 相邻，那么就一定不存在一个排列覆盖到这个位置。假设不成立，必要性得证。
充分性：考虑从空序列开始依次加入若干个序列得到最终的序列。记 \(B_i\) 为当前元素 \(i\) 还需要放多少个。将所有满足 \(B_i=y\) 的元素 \(i\) 取出，按任意顺序排列得到序列 \(S\)，其他元素按任意顺序排列得到序列 \(T\)。我们在 \(P\) 中依次加入序列 \(T,S,T\) 即可。这样的构造可以始终满足 \(x\le 2y\) 的条件，充分性得证。
接下来我们仍然考虑用依次加入若干序列的方式构造最终的序列。
假设当前序列为 \(P\)，最后 \(k\) 个元素按顺序组成的序列为 \(Q\)，第 \(i\) 个元素还需要 \(B_i\) 个。
显然 \(Q\) 一定是一个排列。
令 \(x=\max B_i,y=\min B_i\)，则有解的充要条件为：
- \(x\le 2y+1\)；
- 若 \(x=2y+1\)，则还需要满足 \(Q\) 中所有 \(B_i=x\) 的元素 \(i\) 在所有 \(B_j=x\) 的元素 \(j\) 的前面。
第一个条件的必要性：类似于之前有解条件的必要性证明，需要注意第一个 \(B_i=x\) 的元素 \(i\) 可以和前面部分组成一个排列，所以需要删去。
第二个条件的必要性：可以假设存在一个 \(B_j=y\) 的元素 \(j\) 和 \(B_i=x\) 的元素 \(i\) 满足 \(j\) 的位置在 \(i\) 前面，观察 \(x\le 2y+1\) 的必要性证明，可以发现此时第一个元素不能与前面组成排列，不能删去，那么此时必须满足 \(x\le 2y\)，与 \(x=2y+1\) 矛盾，假设不成立，得证。
充分性：假设最后一个满足 \(B_i=x\) 的元素 \(i\) 为 \(Q\) 中第 \(s\) 个。考虑在 \(P\) 的末尾加入 \(Q_1,Q_2,\ldots,Q_s\)，此时 \(y\) 不变，\(x\) 一定减 \(1\)，所以此时满足 \(x=2y\)，一定有解。充分性得证。
有了以上两个结论后，我们就可以构造字典最小的解了。
考虑每次枚举加入的元素个数 \(s\)，则此时加入的一定是 \(Q_1,Q_2,\ldots,Q_s\) 的一个排列，那么我们就可以确定加入以后的 \(B_i\)，于是可以求出新的 \(x\) 和 \(y\)。分三种情况：
- 若 \(x\le 2y\)，则直接从小到大排序后加入即可；
- 若 \(x=2y+1\)，我们将 \(B_{Q_i}\in \{x,y\}\) 的元素 \(Q_i\) 放在序列 \(f_1\) 中，其余元素放在 \(f_2\) 中。\(f_1\) 优先按是否为 \(y\) 进行排序，都是 \(y\) 或都是 \(x\) 则按大小排序；\(f_2\) 直接按大小排序。然后将 \(f_1\) 和 \(f_2\) 归并即可。注意需要判断最终的序列是否合法。
- 若 \(x>2y+1\)，则直接无解。
时间复杂度 \(O(K^2\sum a_i)\)。
F - Forbidden Tournament
题意
求满足以下条件的 \(N\) 个点有标号竞赛图数量：
- 每个节点入度不超过 \(K\)；
- 不存在四个互不相同的节点 \(a,b,c,d\) 满足，同时存在 \(a\to b,b\to c,c\to a,a\to d,b\to d,c\to d\) 这六条边。
\(N\le 200\)
题解
令图 \(H=(\{a,b,c,d\},\{(a,b),(b,c),(c,a),(a,d),(b,d),(c,d)\})\)，即不能出现的子图。下文中，在不会引起歧义的前提下，会使用一个点集来表示一个诱导子图。
接下来我们考虑一个合法的竞赛图 \(G\) 的结构。
首先我们不断将入度为 \(0\) 的节点删去，假设删去了 \(s\) 个节点，则现在 \(G\) 变为了一个 \(N-s\) 个点，入度不超过 \(K-s\) 的强连通竞赛图。
接下来我们任选 \(G\) 中的一个节点 \(v\)，将所有存在边 \(v\to w\) 的节点 \(w\) 组成的集合记为 \(Y\)，其余节点记为 \(X\)，注意 \(v\in X\)。
竞赛图有性质：若一个竞赛图中存在环，则该图中一定存在三元环。
那么假设 \(X\) 中存在环，那么一定存在不包含 \(v\) 的三元环，那么这个三元环与 \(v\) 一起会组成 \(H\)，不合法，所以 \(X\) 一定是一个 DAG。我们将这些节点按拓扑序记为 \(x_1,x_2,\ldots,x_k\)，那么有 \(x_i\to x_j\) 当且仅当 \(i < j\)。
因为不存在入度为 \(0\) 的点，那么一定存在 \(w\in Y,u\in X\) 满足存在边 \(w\to u\)。假设存在一个点 \(w'\in Y\) 满足存在边 \(w\to w'\)，那么一定存在边 \(w'\to u\)。这是因为如果存在边 \(u\to w'\)，则 \(u,v,w,w'\) 会构成 \(H\)，不合法。
然后我们可以推导出对于 \(w\) 能到的所有在 \(Y\) 中的点 \(w''\)，都存在边 \(w''\to u\)。那么 \(w\) 能到的在 \(Y\) 中的点一定不会有环，因为如果有环，就会有三元环，就会与 \(u\) 组成 \(H\)，不合法。
对于 \(w\) 不能到的所有在 \(Y\) 中的点 \(z\)，一定存在边 \(z\to w\)，那么如果这些点中存在环，又会与 \(w\) 组成 \(H\)，不合法。
综合以上两部分，我们证明了 \(Y\) 也是一个 DAG，我们可以将 \(Y\) 中的节点按拓扑序记为 \(y_1,y_2,\ldots,y_l\)。
接下来我们只要考虑 \(X,Y\) 之间边的方向。
根据上面的讨论，我们得到了一个引理：如果存在边 \(y_j\to x_i\)，那么对于所有 \(j\le j'\le l\)，都存在边 \(y_{j'}\to x_i\)。
根据这个引理，假设存在边 \(x_1\to y_l\)，那么对于所有 \(1\le j\le l\)，都存在边 \(x_1\to y_j\)，这与 \(x_1\) 入度大于 \(0\) 矛盾，所以一定存在边 \(y_l\to x_1\)。
接下来我们证明，对于所有 \(2\le i\le k\)，假设存在边 \(x_i\to y_l\)，那么对于所有 \(i < i' \le k\)，一定存在边 \(x_{i'}\to y_l\)。假设存在边 \(y_l\to x_{i'}\)，那么 \(x_i,y_l,x_1,x_{i'}\) 构成了 \(H\)，不合法。也就是说，存在边 \(y_l\to x_i\) 的 \(i\) 一定是一个前缀 \(\{1,\ldots,t\}\)。
我们还可以证明，对于所有 \(1\le i\le t,1\le j\le l-1\)，若存在边 \(x_i\to y_j\)，那么对于所有 \(i < i' \le k\)，都存在边 \(x_{i'}\to y_j\)。假设存在边 \(y_j\to x_{i'}\)，根据引理一定存在 \(y_l\to x_{i'}\)，那么 \(x_i,y_j,y_l,x_{i'}\) 构成了 \(H\)，不合法。
我们可以将上面的结论推广到 \(1\le i\le k\) 的情况，此时我们需要证明当所有 \(1\le i''\le t\) 都存在边 \(y_j\to x_{i''}\) 时，对于 \(t < i < i' \le k\)，若存在边 \(x_i\to y_j\)，则一定存在边 \(x_{i'}\to y_j\)。假设存在边 \(y_j\to x_{i'}\)，则 \(x_{i''},x_i,y_j,x_{i'}\) 会构成 \(H\)，不合法。
根据上面的结论，我们可以发现对于所有 \(1\le j\le l\)，都存在一个 \(p_j\) 满足，对于所有 \(1\le i\le p_j\)，存在边 \(y_j\to x_i\)；对于所有 \(p_j < i\le k\)，存在边 \(x_i\to y_j\)。
根据引理，我们可以得到 \(p_j \le p_{j+1}\)。
另外我们还需要满足 \(0\le p_j < k, p_l\ge 1\)。
可以发现只需要满足这三个条件就可以唯一构造出一个不存在 \(H\) 的强连通竞赛图 \(G\)。
那么我们只需要计算 \(p\) 的方案数，DP 即可，注意判断当前的状态是否满足度数限制。
一次 DP 复杂度 \(O(kl)\)，总复杂度 \(O(N^4)\)。
值得一提的是，序列 \(p\) 的方案数等价于不能经过两条直线的路径方案数，可以用容斥与组合数学优化到更低的复杂度。
