2026 Summer Day25

T1 网格排列

考场上想到了这道题的 $20\%$ ，但是数数练的还是太少了，所以不会推式子，遂倒闭。

发现可以把题目的条件转化成若干偏序限制，可以进一步把限制拆成上排顺序、下排顺序、两排如何交错。第 $i$ 个限制还对前面出现的数字的个数有要求，所以可以考虑把这些状态放到一个 $n \times n$ 的网格上，把合法的交错方式看成是一条 $(1, 1)$ 到 $(n, n)$ 的一条网格路径。然后呢？然后不会了zzz。

书接上回，对于没有限制对的格子 $T_c$ ，考虑离他最近的右边的有限制的格子为 $T_r$ ，则 $T_c$ 的排名不能超过 $r-1$ 。再考虑下排格子对他的限制，如果他右边第一个给定的下排格子为 $B_p$ ，此时上排确定了 $i$ 个位置，那么他的排名也不能超过 $i$ ，所以这个格子的转移贡献为

V_T(c) = \min(r - 1, i) - c + 1

对下排格子 $B_c$ 同理对称分析，可以得到贡献为

V_B(c) = c - \min(l, j)

其中 $l$ 表示离他最近的左边的有限制的格子。 $j$ 表示上排左边离他最近的给定格子 $T_j$ 。

然后令 $dp_{i, j}$ 表示当前在网格上的状态为 $(i, j)$ ，就是向右和向下走的贡献之和。

T2 树上游戏

题目链接

发现只需要考虑两个相邻节点都是黑色的情况。令 $L_{x \to p}$ 表示这些连通子树里从 $x$ 开始先手必败的数量， $W_{x \to p}$ 表示先手必胜的数量， $C_{x \to p}=L_{x \to p} + W_{x \to p}$ 。则

C_{x \to p} = \prod_{y \ne p} (1 + C_{y \to x}) \\ L_{x \to p} = \prod_{y \ne p} (1 + W_{y \to x}) \\ W_{x \to p} = C_{x \to p} - L_{x \to p}

换根统计一下即可。最后答案为

L_{u \to v} L_{v \to u}+W_{u \to v}W_{v \to u} ​