2026-04-18(#11.5)：第三大道

Sound Souler —— 3rd Avenue

感谢 @laerav 的帮助。

花絮：本来是团队赛，但是改成个人赛了，于是把最难的两个题删掉了。

难度被严格控了，更比拼谁不会卡题而不是谁能做出难题一点。

A. Xor Magic Square

$n$ 为偶数是好做的。

$n$ 为奇数按照模 $4$ 分类，大致是一条对角线上全填 $3$ 和一个 $1$ 一个 $2$ ，剩余的保证每行每列都是一个 $2$ 一个 $3$ 剩下全是 $1$ 。容易构造出合法的答案，更容易证明没有更小的答案。代码。

这一坨组合数乘积相当于在 $n$ 个数中选择 $q$ 轮，第一次给 $a_1-a_2$ 个染色，最后给 $a_q$ 个染色，总共有 $q+1$ 种颜色。

于是 $f(q)=(q+1)^n$ ，直接计算。代码。

由最小瓶颈生成树的定义，如果有解答案只能是最小生成树。因此直接求出一棵最小生成树然后判断每条边的长度是否大于等于树上距离即可。代码。

由排序不等式，倒着扫直接贪心即可。代码。

$x,y$ 坐标是独立的，分别考虑。即 $\begin{cases}t\equiv 0\pmod {2n} \\ t\equiv 0\pmod {2m} \end{cases}$ ，所以答案是 $2nm/\gcd(n,m)$ 。

实际上说的这是个 DAG，只要在这个 DAG 上连通的路径，都可以被统计到答案中。画一画可以发现答案是 $m-n+2$ 。

证明的话只需要一开始找一条路径。对于一个未被访问过的边，我们可以沿着它去扩展。连通一个点需要消耗一条边。代码。

首先这个往下滑是假的，因为对答案没有影响。

模拟往右滑动的过程。维护的是竖着的一段一段的滑动，因此不难想到去维护差分数组。