2025 牛客暑期多校 Round 3 题解
A
容易发现可以把行列关于对角线对称，因此只需考虑行的情况。
对于第 i 行，我们从左往右填入 0 \sim f_i - 1 的数，但此时可能出现 a_{i,j}=f_j 的情况使得影响之前构造好的部分。
考虑到 a_{i,i} 只会影响到第 i 行/列，同时若同时出现两个数 j_1,j_2 满足 a_{i,j_1}=f_{j_1},a_{i,j_2}=f_{j_2}，那么可以直接交换这两个数消去这两个数的影响。
那么解法是显然的了：对于 a_{i,j}=f_j 的情况，优先进行两两配对，最后若仍剩下一个没被配对，则与 a_{i,i} 配对即可。
B
显然当且仅当 a=b=0,c \neq 0 时无解。
构造的思路是显然的，我们先想办法令 a=c,b=0，然后再将 b \leftarrow a \oplus b 即可得到 a=b=c。
具体做法是，我们不断调整 b 的最高位所在位置，然后当该位上 a 与 c 不同时令 a \leftarrow a \oplus b 即可。
实现有一些细节。
C（待补）
D
若初始能进行任何合法操作，答案为 n；否则答案为初始时 1 的个数。
E
假设目标是将所有数变为 L = \text{lcm}(a_1,a_2,\dots,a_n)。
将 \frac{L}{a_i} 质因数分解，计算 n 个数中每个质因子出现的次数。容易发现若所有质因子出现的次数均为偶数，那么一定可行。
那么若 n 为奇数且某个质因子 p 出现次数为奇数，则可以调整 L 为 pL，这样可以使 p 的出现次数变为偶数。
因此 n 为奇数时一定可行。
若 n 为偶数，此时无法操作质因子的奇偶性，因此可行的充要条件即为 \frac{L}{a_i} 中所有质因子出现的次数均为偶数。
显然，\frac{L}{a_i} 中所有质因子出现的次数等价于 a_i 中质因子出现的次数，因此质因数分解统计次数即可。
注意常数。
F
首先 n \le a 无解。
其次 n \mod (a + b) \in [1, a] 时答案为 n \mod (a + b)，剩余情况为 0。
G（待补）
H
需要发现任意时刻可达的点是一个包含根的极大连通块。
维护这个连通块，每次给出一个 (u,l,r) 则意味着连通块向 u 这个位置伸出 r-l+1 步。
使用倍增找到伸出的末端节点，因为每个点的答案只会被更新一次，所以暴力跳父亲更新答案即可。
时间复杂度 \Theta(n \log n)。
I（待补）
J
倒推可以发现，若游戏能结束，轮数一定不超过 \lfloor \log(x+y) \rfloor。
所以卡住上限暴力即可。
赛时写的直接模拟 + 剪枝，也可以通过。