The 2nd Universal Cup Semifinals: Analysis Report
This is the draft of the problems of the 2nd Universal Cup Semifinals. We expect to officially release a version of this document in a few weeks. If you find an error, please send an e-mail to [email protected] or a private message to me (@Qingyu) about it.
Summary
To be added..
A. Records in Chichén Itzá
Proposed by bulijiojiodibuliduo. Prepared by Qingyu and quailty.
Additional acknowledgement to xyz2606, kostka and xiaowuc1 for their contributions to the improvement of the problem statements.
Consider the number of non-leaf vertices, i.e, vertices with degree $\geq 2$, and there are some cases as follows:
- If there are at most $2$ non-leaf vertices: the tree must be a star or a double star (formed by two stars via joining two of their centers by an edge), and it is unique.
- If there are at least $3$ non-leaf vertices, and their degrees are not all the same: in this case, there are at least two different orders in which $3$ of these vertices can be joined, so the tree is not unique.
- If there are at least $4$ non-leaf vertices, and their degrees are all the same but not $2$: in this case, there are at least two different structures in which $4$ of these vertices can be joined, so the tree is also not unique.
- Otherwise: all non-leaf vertices form a unique chain, and therefore the tree is also unique.
B. Almost Convex 2
Proposed by quailty. Prepared by quailty and xyz2606.
Additional acknowledgement to xyz2606 for his contributions to the improvement of the statements.
This problem is a fun variant version of Almost Convex, which was used in The 2nd Universal Cup Stage 17 Jinan.
Choose the lexicographically smallest point as $p_1$, count the number of points inside all triangles $p_1p_ip_j$ in $O(n^3)$ time complexity, which allows us to determine whether a triangle $p_kp_ip_j$ has points inside (excluding the boundary) in $O(1)$ time complexity. Now consider each possible value of $|Q|$:
- $|Q|=|R|$: it is the convex hull $R$;
- $|Q|=|R|+1$: cut an edge $vw$ on $R$ and find a $u \notin R$, where no points are inside the triangle $uvw$ (excluding the boundary), then link $uv$ and $uw$ to obtain $Q$. There are $O(n^2)$ candidates;
- $|Q|=|R|+2$: on the basis of $|Q|=|R|+1$, cut an edge $v'w'$ on $Q$ and find a $u' \notin Q$, where no points are inside the triangle $u'v'w'$ (excluding the boundary), then link $u'v'$ and $u'w'$, and ensure that the resulting figure is a simple polygon. There are two cases here:
- $v'w'$ is not an edge on the initial $R$: there are only $2$ such edges, and it is possible to enumerate the edges and $u'$ for checking in $O(n)$. Since there are only $O(n^2)$ $Q$ satisfying $|Q|=|R|+1$, the time complexity is $O(n^3)$;
- $v'w'$ is an edge on the initial $R$: it is equivalent to selecting the aforementioned $uvw$ and $u'v'w'$ in $R$, requiring that there are no points inside the triangles $uvw$ and $u'v'w'$, and these two triangles do not intersect. Consider enumerating $u$ and $u'$, the line passing through these two points divides $R$ into two sides, and only when $vw$ and $v'w'$ are on the same side, the two triangles may intersect. To calculate the answer, enumerate $vw$ and use two pointers to maintain the range of $v'w'$. The time complexity is also $O(n^3)$.
C. Space Station
Proposed by Kubic (a.k.a. vme50). Prepared by Lynkcat and Qingyu.
Additional acknowledgment to xyz2606 and xiaowuc1 for contributions to improving the problem statements, and to Kevin5307 for further testing the problem.
Analysis will be added a bit later.
D. Solar Panel Grid Optimization
Proposed by lanos212. Prepared by lanos212 and Qingyu.
Additional acknowledgement to bulijiojiodibuliduo and Lynkcat for their contributions to the improvement of the problem.
Analysis by cmll02.
首先考虑下面过程：
从左往右枚举每一列 $c(1\le c < n)$，先对 $a_{n,c}=b_{i,c}$ 的 $i$ 执行 row i，然后执行 $n$ 次 column n ，再把刚才没操作的行 $i$ 执行 row i。容易发现，对于一个 $c$ 执行完上述操作后，$a$ 的第 $n-1$ 列会与 $b$ 的第 $c$ 列相同。
执行完后，最后一列可能不满足要求。
观察到执行完上面操作后，$a$ 每行 $1$ 的个数的奇偶性的变化是固定的：row 操作不会改变行奇偶性，连续 $n$ 次 column n 会同时改变每行的奇偶性。所以如果能够先处理 $a$ 的行奇偶性和 $b$ 的行奇偶性完全相同/相反（取决于 $n$ 的奇偶性）即可。
这样就可以先计算出每一行需要将 $a_{i,n}$ 调整为多少，记这个值为 $A_i$。
现在只要调整奇偶性。先把第 $n$ 列和第 $n$ 行变成全 $0$，然后再把第 $n$ 行 column n $n$ 次变成全 $1$。由于将所有 $01$ 反转实际上没有区别，下面假设第 $n$ 行和第 $n$ 列的 $2n-1$ 个数中 $1$ 比 $0$ 多。
考虑将第 $n$ 行和第 $n$ 列先全部变成全 $0$，然后再由全 $0$ 还原出目标奇偶性。
要将第 $n$ 行和第 $n$ 列先全部变成全 $0$，可以先把第 $n$ 列清零。这一步的做法是执行 $n$ 次“不断执行 row n 直到 $a_{n,n}=1$，然后 column n”。这样会把 $n$ 个 $1$ 变成 $0$ 并放到第 $n$ 列。
接下俩把第 $n$ 行清零。这一步只要不断把第 $n$ 行的 $1$ 用 row n 放到 $(n,n)$ 的位置，然后 column n。
完成到这一步之后，column n $n$ 次，把第 $n$ 列变为全 $1$。此时 $a$ 会长下面这个样子
???...?1 ???...?1 ???...?1 ???...?1 . . . . . . 000...01
先忽略掉 $A_n$，解决掉 $A_1\cdots A_{n-1}$。类似最开始说的东西，依次考虑 $A_{n-1}\cdots A_1$，如果是一个 $1$ 就从第 $n$ 行拉一个 $0$ 过来然后 column n，否则直接 column n。对于第 $n$ 行的奇偶性，调整是简单的。
前面部分的操作次数是 $2n(n-1)$，调整奇偶性的次数是 $O(n)$ 的。可以通过。
E. Fast Median Transform
Proposed by djwj233. Prepared by djwj233 and Lynkcat.
Additional acknowledgement to xiaowuc1 and kostka for their contributions to the improvement of the problem statements.
我们考虑怎么对于单次询问求出 $\text{FMT}(a,b,X)$ 的值。
sub1 可以直接输出 $0$，sub2 可以直接暴力模拟题述过程。
显然通过二分答案可以以一个 $\log V$ 的代价（也可以通过离散化变成 $\log (n+m)$）把问题转化为 $V=2$。
有一个观察：
- 在 $V=2$ 时，若一次操作中 $a_i=b_j=0$，那么就是 $X\gets 0$，同样 $a_i=b_j=1$ 就是 $X\gets 1$，而 $a_i\ne b_j$ 不会改变 $X$。
对 sub3，答案就是 $X$；对 sub4，只需判断 $y$ 中有没有 $0$ 即可。
对 sub5，我们设 $a$ 中 $1$ 的位置分别为 $p_1,p_2,\cdots,p_k$（$k\le 5$）。
考虑从 $nm-1$ 倒着找到最后一次赋值操作，设 $b_{p_1}$ 最后一次被操作到是 $(a_{p_1},b_{q_1})$，那么如果它不是赋值操作一定有 $b_{q_1}=0$。
我们考虑 $b_{q_1}$ 的最后 $6$ 次操作，由于 $\gcd(n,m)=1$，所以这 $6$ 次操作操作到的数两两不同，而且其中一定有一个不在 $p$ 中。
也就是说，这里可以证明最后一次赋值操作离 $nm-1$ 的距离最多是 $6(n+m)$，我们倒回去找这么多步就可以确定 $A$ 的值。
对 sub6 我们猜想也有类似的结论。
具体地，取出最后的 $d=2(n+m)$ 次操作，我们证明其中必有一次赋值操作，否则所有 $nm-1$ 次操作中都没有赋值操作。
反证法，我们取出一个 $i$，可知最后 $d$ 次操作中一定有两次操作到了 $i$，不妨设操作的是 $(a_i,b_{j_1}),(a_i,b_{j_2})$。
这样如果 $a_i=1$ 且这不是一次赋值操作，则必有 $b_{j_1}=b_{j_2}=0$，反之亦然。
我们以此建立一个二分图，对于这 $d$ 次操作，对左部点的 $i$ 和右部点的 $j$ 连边即可，显然每个点度数至少为 $2$。
我们只需要证明，这张二分图必然是连通图即可。
（因为假如最后 $d$ 次操作中没有赋值操作，那么可以推得左部点都是 $1$，右部点都是 $0$（或其对称情况），答案就是 $X$）
我们考虑二分图中的任意一个连通块，设其中右部点的集合为 $S$。
对于 $S$ 中的任意一个 $j$，设最后一次操作到它是 $(a_i,b_j)$，考察包含 $a_i$ 的前一次操作 $(a_i,b_{j^\prime})$。
易证这在最后 $d$ 次操作中，即 $j^\prime\in S$，而且有 $j^\prime\equiv j-n\pmod{m}$。
也就是说，$\forall j\in S, (j-n)\bmod m\in S$，而由于 $\gcd(n,m)=1$，所以一定可以不断“跳跃”直至证明 $S$ 就是全集。
左部点是同理的，也就是说整张二分图必然是连通图，证毕。
简单地说，我们证明了如下事实：
设 $\varnothing \ne S\subseteq \{0,1,\cdots,m-1\},d\perp m$，则 $S\equiv S+d\pmod{m}$ 当且仅当 $S$ 为全集。
对于一般情况，设 $c=\gcd(n,m)$，判掉无赋值操作后可以证明操作一定在最后 $2(n+m)$ 次中。
设 $n,m$ 同阶，复杂度 $\mathcal O(n\log n)$ 或 $\mathcal O(n\log V)$。
此外也有一个思路比较朴素且套路的 $\mathcal O(n\log^2n)$ 做法，大致是在二分答案后从解方程的角度入手。
事实上若我们仔细分析一下这个二分的本质，是可以把这个二分省去的：
我们只需要直接顺序模拟后 $2\max(n,m)$ 操作也是正确的。这是单次 $\mathcal O(n)$ 做法。
在 $n,Q\le 5\times 10^5$ 的部分，我们显然无法每次都重新求一遍答案。
下记 $U(x,y)= \begin{cases} [x,y] & x\le y\\ [y,x] & x>y\\ \end{cases}$.
考虑 sub11，这里我们不会做任何修改，只是对不同的 $X$ 求答案。
我们维护一个区间 $[L,R]$，初始为 $[0,+\infty)$，之后倒着枚举所有操作，每次把维护的区间和当前区间取交。
若某时刻交为空则答案已经可以确定，否则当且仅当 $X_0\in [L,R]$ 时答案为 $X_0$，否则视 $X_0$ 的大小为 $L$ 或 $R$。
上面的证明过程已经给出只需枚举后 $2\max(n,m)$ 次操作即可。
这样我们可以求出一个区间 $[L,R]$，然后按照 $X_0$ 的大小确定答案。
在 sub12 中，我们观察到这个区间可以直接合并，构成了半群。
我们取出后 $2\max(n,m)$ 次操作，直接使用线段树维护之。由于 $n\ge m$ 所以每次操作只会修改至多 $2$ 次操作，复杂度 $\mathcal O((n+Q)\log n)$。
考虑 sub13，依然沿用与上面相同的思路，但是考虑根号分治。在下面的复杂度分析中我们记 $N=\max(n,m)$。
下面我们需要用到一个引理：
- 引理：对于一些区间 $[l_i,r_i]$，设 $L=\max l_i,R=\min r_i$，它们的交为 $\bigcap_i [l_i,r_i]=\begin{cases} \varnothing & L>R \\ [L,R] & L\le R \end{cases}$.
证明：
我们先分类讨论证明 $n=2$ 时成立，细节略。
然后使用归纳法，对于 $n=m+1$ 时的情况，可以由归纳假设转化为 $n=2$ 时的情况。
具体地，若 $n\ge B$ 则每次操作只会修改至多 $\mathcal O(\frac{N}{B})$ 次操作的信息，直接使用线段树维护之，可以做到 $\mathcal O(\frac{N^2\log N}{B})$ 的复杂度。
否则有 $n\le B$，我们考虑对每次询问 $\mathcal O(B\log N)$ 地求出答案。
具体地，我们先考虑如何判断所有区间的交集是否为空集。
容易发现，对于一个特定的 $a_i$，在所有与其配对的 $b_j$ 中，只有 $\ge a_i$ 的最小值和 $\le a_i$ 的最大值（如果存在）这至多两个是有效的。
这是可以在直接 $\mathcal O(n)$ 次二分查询出这两个数然后对区间求交得到，复杂度 $\mathcal O(NB\log N)$。
若区间不为空则答案可以直接确定，否则我们考虑找到一个最大的 $d$ 使得只考虑 $i\in [d,nm-1]$ 中的操作时所有区间的交不为空。这样我们直接讨论第 $d-1$ 次操作的位置关系即可得解。
不难发现，这个过程可以由两部分实现：
给定一个 $d$，求只考虑 $i\in [d,nm-1]$ 中的操作时所有区间的交：
我们可以对于每个 $a_i$ 把所有涉及到它的 $b_j$ 找出，按时间排序后作后缀最大 / 最小值。
在每次询问时对每个 $a_i$ 找到 $d$ 及之后的第一次操作，$\mathcal O(1)$ 地查询对应位置的最大、最小值即可做到总复杂度 $\mathcal O(n)$。
求出 $d$：
我们二分一个 $d$，每次判定使用上面的算法，可以做到 $\mathcal O(n\log N)$。
取 $B=\sqrt{n}$，总复杂度可以做到 $\mathcal O(N\sqrt{N}\log N)$。
（若继续优化上面 $n\le B$ 的过程或许也可以做到 $\mathcal O(N\sqrt{N\log N})$）
如何做到 $\mathcal O(N\log N)$，通过 sub14？下称 $MX = nm-1,L=2\max(n,m)$。
自然地，我们对 $n\ge m$ 和 $n< m$ 分类讨论。对于 $n\ge m$ 由上可以直接维护，下面认为有 $n < m$。
考虑把操作倒过来考虑：对 $i\in [0,L)$，设第 $MX-i$ 次操作的数为 $(a_{p_i},B_i)$。
我们考虑维护 $n$ 个数列 $A_{0\cdots n-1}$，生成方式是依次对于每个 $i\in [0,L)$，将 $B_i$ 将其插入 $A_{p_i}$ 末尾。
举个例子，样例中 $n=2,m=3,a=[1,3],b=[4,2,3]$ 时，有 $L=6$，那么：
- $B=[3,2,4,3,2,4]$；
- $p=[1,0,1,0,1,0]$.
- $A_0=[2,3,4]$, $A_1=[3,4,2]$.
由于 $b$ 数列不会改变，容易发现 $B,p,A_i$ 都是确定的。
容易发现 $A_i$ 非空，且长度在 $\left\lfloor\frac{L}{n}\right\rfloor$ 和 $\left\lceil\frac{L}{n}\right\rceil$ 之间，所有 $A_i$ 的长度之和为 $L$。
我们考虑先判断是否对于全部的 $L$ 个区间，其交都不为空。
这个问题是容易解决的，容易发现有： $$ \forall i, \bigcap_{x\in A_i}U(x,a_i)=U(a_i,\max_{x\in A_i,x < a_i} x)\cap U(a_i,\min_{x\in A_i,x\ge a_i} x) $$ 也就是说，对于我们只需要对于每个 $a_i$ 维护至多两个区间然后求它们的交即可。
这可以通过维护左端点的 $\max$ 和右端点的 $\min$ 解决，而这可以直接使用 C++ STL muliset 在 $\mathcal O((n+Q)\log n)$ 内维护。
若全部区间的交不为空，那么依据上面的分析我们可以直接得到答案。
否则，我们依然采用上面的思路：找到一个时间点 $T$ 使得：
- $\displaystyle \bigcap_{i=0}^{T-1}U(A_{p_i},B_i)\ne \varnothing$.
- 设 $\displaystyle Z=\bigcap_{i=0}^{T}U(A_{p_i},B_i)$, 有 $Z=\varnothing$ 或 $\exists u, Z=[u,u]$.
无论是哪种情况，我们在找到一个这样的时间点 $T$ 之后，求出 $Y=\displaystyle \bigcap_{i=0}^{T-1}U(A_{p_i},B_i)$，讨论 $U(A_{p_T},B_T)$ 与 $Y$ 的位置关系即可得到答案。（因为此时答案一定是 $Y$ 的一个端点）
类似 $n\ge m$ 中的那样，我们对于使用线段树维护 $\displaystyle \bigcap_{i=0}^{n-1}U(A_{p_i},B_i)$ 的值。
（由于每次操作只会修改线段树中维护的至多一个区间，这部分的复杂度是 $\mathcal O(N\log N)$。）
设 $\displaystyle Z_0=\bigcap_{i=0}^{n-1}U(A_{p_i},B_i)$，若 $Z_0=\varnothing$ 或 $\exists u, Z_0=[u,u]$ 那么我们可以直接在线段树中确定答案。
否则，考虑推理此时的性质。
对于 $i\in [0,n-1]$，显然 $a_i\ne A_{i,0}$。若 $a_i < A_{i,0}$ 那么我们记 $c_i=0$，否则 $c_i=1$。（$c_i$ 可以在修改时直接维护）
若 $\exists i,j, a_i\le a_j,c_i>c_j$ 则可以证明 $Z_0=\varnothing$ 或 $\exists u, Z_0=[u,u]$，矛盾。
因此，$\exists V, \forall i, c_i=[a_i\le V]$。我们可以使用 multiset 维护 $LB=\max_{c_i=0}\{a_i\},RB=\min_{c_i=1}\{a_i\}$，这样一定有 $LB < RB$。维护的复杂度是 $\mathcal O(N\log N)$。
对于 $t\ge n-1$，记 $\displaystyle Z_t=\bigcap_{i=0}^{t}U(A_{p_i},B_i)$，可以证明，$\exists u < v, Z_t=[u,v]$（下称其为符合条件）当且仅当： $$ \min(RB,\min_{i\le t,c_{p_i}=0} B_i) > \max(LB,\max_{i\le t, c_{p_i}=1} B_i) $$ 由于 $Z_{n-1}$ 符合条件，至少应有 $\min_{c_i=0} A_{i,0}>\max_{c_i=1} A_{i,0}$ 成立。
我们把 $0\cdots n-1$ 按照 $A_{i,0}$ 升序排序后得到 $q_i$，也即找到一个 $\{0,1,\cdots,n-1\}$ 的排列 $q$ 使得 $\forall i\le j, A_{q_i,0}\le A_{q_j,0}$。再记 $w=q^{-1}$ 为 $q$ 的逆排列。
那么由于 $Z_{n-1}$ 符合条件，因此必然有 $\exists K, [c_{q_i}=0]=[i\ge K]$，其中 $K=\sum_{i=0}^{n-1}[c_i=1]$。
我们考虑如何求出 $\min_{i\le t,c_{p_i}=0} B_i$ 的值。
不妨设 $t=xn+y$，其中 $y\in [-1,n-2]$，我们考虑把问题分成两个部分：
- 求 $\min_{i < xn,c_{p_i}=0} B_i$.
由于 $p_{0,\cdots n-1}$ 构成了 $\{0,1,\cdots,n-1\}$ 的排列且 $p_i=p_{i\ \bmod \ n}$，因此根据上面的结论，可以证明： $$ \min_{i < xn,c_{p_i}=0} B_i=\min_{w_{i}\ge K,j < x} A_{i,j} $$ 对 $A$ 预处理出二维前缀 $\min$ 后，单次查询可以做到 $\mathcal O(1)$.
- 求 $\min_{xn\le i \le xn+y,c_{p_i}=0} B_i$.
可以发现 $\min_{xn\le i \le xn+y,c_{p_i}=0} B_i=\min_{i\ge n-1-y,w_{i}\ge K} A_{i,x}$.
这是一个二维偏序问题，可以使用可持久化线段树维护。
由于 $x\in[0,\left\lceil\frac{m}{n}\right\rceil-1]$，我们在这里可以维护 $\left\lceil\frac{m}{n}\right\rceil$ 棵可持久化线段树实现上面的查询，这部分的代码实现难度较大。
求 $\max_{i\le t, c_{p_i}=1} B_i$ 是同理的。
综上所述，我们可以在一次二分后以单次 $\mathcal O(\log N)$ 的时间判断 $Z_t$ 是否符合条件。因此我们可以 $\mathcal O(\log^2 N)$ 地找到上面的 $T$，从而求出答案。这是 $\mathcal O(N\log^2 N)$ 的做法，进行一些常数优化后可能可以通过。
要优化到 $\mathcal O(N\log N)$ 是很简单的。
我们可以先二分出一个 $x$ 满足 $xn\le T<(x+1)n$。
在这部分二分中，我们可以单次 $\mathcal O(1)$ 地判断 $x$ 是否合法，所以复杂度是 $\mathcal O(\log N)$。
然后我们再二分出 $T$ 的精确值。
这可以通过在可持久化线段树上二分实现，所以复杂度依然是 $\mathcal O(\log N)$。
F. Colorful Graph 3
Proposed by 5ab. Prepared by 5ab.
Additional acknowledgement to Lynkcat, xiaowuc1 and xyz2606 for the contributions to the improvement of the problem statements, and to Kevin5307 and cmll02 for further testing the problem.
若有一个 $c_i\ge 2$，则构造对应颜色的菊花即可。
考虑计算理论最小的边数。设颜色 $i$ 的边数为 $a_i$，并定义 $t_i$ 为：若 $c_i=0$ 则 $t_i=0$，否则为最大的满足 $t_i(t_i+1)\le a_i$ 的整数。则为了保证连通，对于任意 $1\le i\le n$，以下不等式需要满足：
$$ \left(\sum a_j\right)-a_i+t_i\ge n-1 $$
注意到 $a_i-t_i$ 随着 $a_i$ 变大单调不降，所以存在一组最优解，满足 $a_i-t_i$ 的极差不超过 $1$。
假设我们求出了一组最小的 $a_i$，我们考虑两种策略：
$c_i=0$：每次从每种颜色中取出一条边，组成一个环并连接在任意点上，重复直到没有边。这样断掉任意一种颜色的边都是一些连起来的链。
$c_i=1$ 的 exact case：设 $T=\max \{t_i\}$，则先构造一个 $T$ 个点的完全图，然后将每条边替换成每种颜色各一条的链。
对于一般的情况，我们先执行 $c_i=1$ 的策略，并将 $c_i=0$ 的边也插入完全图的链中，但要除去一棵生成树。剩下的边数极差不超过 $1$，沿用 $c_i=0$ 的构造策略即可。可以证明这个构造可以取到下界。
G. CNOI Knowledge
Proposed by Kubic (a.k.a. vme50). Prepared by Kubic (a.k.a. vme50) and quailty.
Additional acknowledgement to kostca for the contributions to the improvement of the problem statements.
Analysis will be added a bit later.
H. Exchanging Kubic 2
Proposed by Kubic (a.k.a. vme50). Prepared by Kubic (a.k.a. vme50), Lynkcat and Qingyu.
Additional acknowledgement to djq_cpp and kostka for the contributions to the improvement of the problem statements.
Analysis will be added a bit later.
I. Nightmare
Proposed by ix35. Prepared by ix35, cmll02, Kevin5307 and Qingyu.
题意即为在维数 $m$ 尽量小的 $\mathbb F_p$ 上线性空间中找到 $n$ 个向量使得 $G$ 是它们的 Gram 矩阵。
$G$ 可以考虑为一个二次型，具体地，假设它是 $\{v_1,\ldots,v_n\}$ 的 Gram 矩阵，则对于 $x=\sum_{i=1}^n x_iv_i$，设 $X$ 是 $x$ 的坐标，那么
$$X^TGX=\sum_{i=1}^n\sum_{j=1}^n x_ix_j\langle v_i,v_j\rangle=\langle x,x\rangle.$$
假设对 $G$ 作合同变换得到 $G'=A^TGA$，其中 $A$ 是 $\{w_1,\ldots,w_n\}$ 坐标到 $\{v_1,\ldots,v_n\}$ 坐标的坐标变换矩阵，则设 $X$ 是 $x$ 在 $\{w_1,\ldots,w_n\}$ 的坐标，那么
$$X^TG'X=(AX)^TG(AX)=\langle x,x\rangle$$
因此 $G'_{i,j}=\langle w_i,w_j\rangle$，我们可以根据 $A$ 反求出 $\{v_1,\ldots,v_n\}$。也就是说，求出任意一个与 $G$ 合同的矩阵的答案，就可以求出 $G$ 的答案。
Part 1：$p>2$
在特征不为 $2$ 的域上，任何二次型都可以合同对角化。具体地，若存在 $G_{1,1}\ne 0$，则令 $v_1\leftarrow \sum_{i=1}^n\langle v_1,v_i\rangle v_i$ 就可以消去第一行第一列所有的 $1$。否则，如果对角元全为 $0$，设 $G_{1,2}\ne 0$，则令 $(v_1,v_2)\leftarrow (v_1+v_2,v_1-v_2)$，则有 $(v_1+v_2)^2-(v_1-v_2)^2=4v_1v_2=\dfrac{2}{G_{1,2}}\cdot 2G_{1,2}v_1v_2$，因此操作后至少有一个对角元非零（注意这里要求 $\dfrac{2}{G_{1,2}}\ne 0$，这需要在特征不为 $2$ 的域上才总是成立）。
设对角化后的矩阵为 $G'=\operatorname{diag}(g_1,\ldots,g_k,0,\ldots,0)$，其中 $g_1,\ldots,g_k\ne 0$。
若 $G'$ 对应的答案为 $\{v_1,\ldots,v_n\}$（$v_i$ 是列向量），我们断言：
- $v_i$ 的长度 $m$ 的最小值为 $k$ 为 $k+1$。
- $m$ 的最小值为 $k$，当且仅当 $g_1,\ldots,g_k$ 中有偶数个非二次剩余。
$m\ge k$ 是显然的，下面首先证明 $g_i$ 有奇数个非二次剩余时 $m>k$：假设 $m=k$，令 $B=[v_1,\ldots,v_n]$，则 $G'=B^TB$，因此 $G'_{[1,k]}=B^T_{[1,k]}B_{[1,k]}$，那么
$$\det(G'_{[1,k]})=\prod\limits_{i=1}^k g_i=(\det(B_{[1,k]}))^2$$
应当是个二次剩余，但是奇数个非二次剩余的乘积是非二次剩余，这导出矛盾。
接下来考虑构造。
- 若 $g_i$ 是二次剩余，则令 $v_{i,j}=0\ (j\ne i),\ v_{i,i}=\sqrt g_i$ 即可。
- 剩下的非二次剩余两两配对，不妨设 $g_1,g_2$ 是二次剩余，令 $v_1=[a,b,0,\ldots,0],\ v_2=[c,d,0,\ldots,0]$。考虑确定 $a,b,c,d$，使得：
$$a^2+b^2=g_1,\\c^2+d^2=g_2,\\ac+bd=0.$$
+ 事实上，任意求出一组 $(a,b)$（容易导出存在 $p$ 组这样的 $(a,b)$），再令 $c=a\sqrt{\dfrac{g_2}{g_1}},\ d=-b\sqrt{\dfrac{g_2}{g_1}}$ 即可。 - 最终若剩下一个非二次剩余 $g_i$，单独凑一个 $a^2+b^2=g_i$ 即可，此时维数会变为 $k+1$。
至于 $(a,b)$ 的求法，显然只要对于某个特定的非二次剩余求出来就行了（别的情况可以类似于求 $c,d$ 的方式归结为求平方根），由于有 $p$ 组这样的 $(a,b)$，随机枚举 $a$ 并检查是否存在对应的 $b$ 即可。
时间复杂度为 $O(n^3+p^{0.25}\log p\log\log p+n\log^2 p)$。
Part 2：$p=2$
在特征为 $2$ 的域上，二次型不一定能对角化，所以上面的做法不再生效。
定义 $J=\begin{bmatrix}0 & 1\\ 1 & 0\end{bmatrix}$。我们断言，$\mathbb F_2$ 上的矩阵一定合同于某个分块对角矩阵，每个对角块为 $[0],[1]$ 或 $J$。
为了实现这一分块对角化，我们首先类似于 $p>2$ 的情况解决对角线上有 $1$ 的情况，接下来规约到了对角线上全为 $0$ 的情况，我们要证明此时一定可以将矩阵合同为以 $J$（以及占位的 $[0]$）为对角块的分块对角阵。事实上假设 $G_{1,2}=1$，那么可以用 $G_{1,2}=G_{2,1}=1$ 把所有其他的 $G_{1,i},G_{2,i},G_{i,1},G_{i,2}$ 都消成 $0$，然后归纳即可。
令得到的分块对角阵为 $G'$，其中对角块为 $[0]$ 的个数为 $a$，$[1]$ 的个数为 $b$，$J$ 的个数为 $c$，我们知道如下事实：
- $a+b+2c=n$，显然。
- $b+2c=r=\operatorname{rank}(G')=\operatorname{rank}(G)$，因此 $a$ 是确定的。
- $b\ne 0\iff \exists i,G_{i,i}=1$，因为如果对角线不全为 $0$，则不可能消成全零；反之亦然。
以上这些事实已经足够充分。若 $G'$ 对应的答案为 $\{v_1,\ldots,v_n\}$（$v_i$ 是列向量），我们断言：
- $v_i$ 的长度 $m$ 的最小值为 $r$ 为 $r+1$。
- $m$ 的最小值为 $r$，当且仅当 $b\ne 0$。
$m\ge r$ 是显然的。下面首先证明 $b=0$ 时 $m>r$：假设 $m=r$，那么 $\{v_1,\ldots,v_n\}$ 就构成空间的一组基，然而由于对角元都为 $0$，所以它们都含有偶数个 $1$，故无法线性组合出有奇数个 $1$ 的向量，这与它们是基矛盾。
接下来进行构造。
- 首先我们构造 $2c$ 个 $2c+1$ 维向量解决所有形如 $J$ 的对角块：首先令 $v_{i,j}=1\iff j\leq i+1$，然后再将所有的 $v_{2i,2i}$ 改为 $0$ 即可。
- 若 $b=0$ 则已经做完，否则，令第 $2c+1$ 个向量为 $v_{2c+1,i}=1\iff i\leq 2c+1$，第 $2c+i\ (i\leq b)$ 个向量为 $v_{2c+i,j}=1\iff j=2c+i$ 即可。总维数为 $2c+b$。
时间复杂度为 $O(n^3)$，可能可以 $O\left(\dfrac{n^3}{w}\right)$。
J. Guess The Sequence 2
Proposed by Kubic (a.k.a. vme50). Prepared by Kubic (a.k.a. vme50) and Kevin5307.
Additional acknowledgement to Lynkcat and xiaowuc1 for the contributions to the improvement of the problem statements.
对于一种选择区间的方案，我们考虑怎样可以还原排列，或说明对应的排列个数大于 $1$。
从小到大考虑每个数。设当前考虑到了 $x$，观察所有满足 $m_i\leq x$ 的区间，若 $1,2,\dots, x$ 中有至少两个数均没有被这些区间覆盖，那么对应的排列个数一定大于 $1$。这是因为，原排列一定是一个满足限制的排列，且在原排列的基础上交换这两个数，仍然满足所有限制，故这种情况是不合法的。同时，在所有没有被 $m_i < x$ 的区间覆盖的数（排除掉上面的情况后，这样的数最多只有两个）中，一定有恰好一个位于 $m_i=x$ 的区间的交中，否则两个数都在 $m_i=x$ 的区间的交中：我们同样可以交换这两个数，使得所有限制仍然被满足。
容易证明，如果同时满足这两个条件，那么一定可以唯一确定排列。于是可以考虑 DP 状态 $f(x,p)$ 表示考虑到了 $x$ 且数 $p$ 没有被覆盖时的方案数，若 $p=0$ 则表示所有数都被覆盖了。分析该 DP 数组的转移。下面令 $x$ 为当前考虑的数，$a$ 为一个满足其在原排列中和 $x$ 之间的所有数都 $\leq x$ 的数，$b$ 为一个满足其在原排列中和 $x$ 之间有至少一个数 $>x$ 的数。
- $f(x-1,0)\to f(x,0)$：这一类要求 $x$ 被覆盖。
- $f(x-1,0)\to f(x,x)$：这一类要求 $x$ 不被覆盖。
- $f(x-1,a)\to f(x,a)$：这一类要求 $x$ 被覆盖的同时 $a$ 不被覆盖。
- $f(x-1,a)\to f(x,0)$：这一类要求 $x$ 和 $a$ 都被覆盖，且要能区分 $a$ 和 $x$，即所有区间的交不能包含 $a$。
- $f(x-1,b)\to f(x,b)$：这一类要求 $x$ 被覆盖。
考虑优化这个 $O(n^2)$ 的 DP。由于数据随机，所以每个 $x$ 要考虑的 $a$ 的总和是 $O(n\ln n)$ 级别的，且每个 $x$ 的所有第 $5$ 类转移的系数都相同，所以可以用全局乘法 tag 做到 $O(n\ln n)$。
K. Game: Battle of Menjis
Proposed by gyh20. Prepared by gyh20.
Additional acknowledgement to xyz2606 for the contributions to the improvement of the problem statements, and feecle6418 for showing in the problem statements.
给出结论：无论游戏进行多少轮，其结果总是和只进行一轮的情况完全一致。
Alice 可以在游戏的第 $2,3,\dots, k$ 轮均选择上一轮中 Bob 选择的位置，也就是将被 Bob $-1$ 的数复原，此时等价于只进行一轮的情况，所以进行 $k$ 轮的答案不会小于进行一轮的答案。类似地，Bob 可以在游戏的第 $1,2,\dots,k-1$ 轮均选择同一轮中 Alice 选择的位置，也就是将被 Alice $+1$ 的数复原，此时同样等价于只进行一轮的情况，所以进行 $k$ 轮的答案不会大于进行一轮的答案。故结论正确。
此时我们可以枚举 Alice 的选择，然后考虑 Bob 的选择。容易发现，Bob 选择的数对最终所有数的异或和带来的改变只取决于他选择的数二进制下末尾 $0$ 的个数，于是可以统计每个二进制下末尾 $0$ 的个数为 $x$ 的数是否存在，然后暴力枚举 Bob 的选择。时间复杂度 $O(n\log a_i)$。
L. Slay the Spire
Proposed by xtqqwq. Prepared by djq_cpp, Lynkcat and xtqqwq.
先假设所有边都能够取到。相当于对于每条边，我们可以支付一个代价，更换其起点。最后要形成一个完整的欧拉回路。那么对于每个点，我们至少要支付 max(0, 出度 - 入度 - 是否是起点 - 到它的药水个数) 条以它为起点的边的代价。我们直接选权值最小的那些边。可以证明这样选之后一定存在一个更换边的起点的方案可以使得最终图上所有点 (入度 + 是否是起点 + 到它的药水个数 = 出度)。唯一问题就是这个最终图是否是一个可以连续走完的连通块。可以发现，只有在存在一个初始图中入度 = 0 的强连通分量，且这些边全都被保留的情况下，才会出现孤立的连通块。这种情况下，我们就需要至少再支付这个强连通分量中一条边的代价。但与此同时，我们就可以少支付一条连出该强连通分量的边的代价。对于所有的这些强连通分量，枚举这样替换的最优解即可。
时间复杂度 $O(m\log n)$。
M. Puzzle: Summon
Proposed by Qingyu. Prepared by Lynkcat and Qingyu.
Additional acknowledgement to bulijiojiodibuliduo for the contributions to the improvement of the problem statements, and quailty for the adjustment of the original problem idea.
Analysis will be added a bit later.
