做题笔记 - 性质题 1

迷向术式(华中地区邀请赛 19th)

注意到路径可以重边，所以在非二分图中可以通过不断绕奇环去改变原有路径长度的奇偶性，也就是非二分图中任意两个不同节点都同时存在长度为奇和偶的路径。相反地，在二分图中任意两个不同节点只存在长度为奇或长度为偶的路径。

如果当前节点 $a_p$ 所在联通块为非二分图，那么只要满足 $a_i$ 在当前联通块内的 $a_i$ 都能够到达。相反地地，如果当前节点 $a_p$ 所在联通块为二分图，满足 $a_i$ 在当前联通块内的同时，满足下列两个条件之一：

• $a_i$ 和 $a_p$ 路径长度为偶数，$i$ 和 $p$ 奇偶性一致；
• $a_i$ 和 $a_p$ 路径长度为奇数，$i$ 和 $p$ 奇偶性相反。

不难发现，无论是二分图还是非二分图，$a_i$ 的连通都具有传递性，即：

传递性：若 $a_i,a_j$ 能够互相到达，且 $a_j,a_k$ 能够互相到达，那么 $a_i,a_k$ 也能够互相到达。

那么我们发现实际上由 $a$ 序列建出的图是若干的完全子图。由于题目中的询问带有下标严格递增的限制，所以子完全图有了方向，变成了传递竞赛图。作为先手只有开局无路可走才会输，否则只要一步跨到最远点就必赢。即只要查询 $a[l+1\dots r]$ 中是否存在与 $a_l$ 在新图中同一完全子图就可以了。离线不难处理。

Snaking Arrangement(CF2232E)

来源：CF Round 1101 E

难度：2600

有趣的性质题，难度几乎都在推导性质上了。

观察到蛇的长度排列很特殊，不妨尝试依据长度正序或逆序进行分析：

---

【逆序推导】

性质 1：对于边长为 $n$ 的正方形中随机剥离一条长度为 $2n-1$ 蛇，剩下的部分要么是一个正方形，要么是两个部分可以拼成一个正方形。

这应该很简单吧，对于任意一个长度为 $2n-1$ 的蛇，起点和终点必然是 $(1,1)$ 和 $(n,n)$。然后我们可以将路径上的所有点全部向右向上平移，然后在左下角留下一个边长 $n-1$ 的正方形 。比如：

┌─────┬─────┬─────┬─────┬─────┐
│  1  │  2  │  3  │     │     │
├─────┼─────┼─────┼─────┼─────┤
│     │     │  4  │  5  │     │
├─────┼─────┼─────┼─────┼─────┤
│     │     │     │  6  │     │
├─────┼─────┼─────┼─────┼─────┤
│     │     │     │  7  │     │
├─────┼─────┼─────┼─────┼─────┤
│     │     │     │  8  │  9  │
└─────┴─────┴─────┴─────┴─────┘

，变成：

┌─────┬─────┬─────┬─────┬─────┐
│  1  │  2  │  3  │  5  │  9  │
├─────┼─────┼─────┼─────┼─────┤
│     │     │     │     │  4  │
├─────┼─────┼─────┼─────┼─────┤
│     │     │     │     │  6  │
├─────┼─────┼─────┼─────┼─────┤
│     │     │     │     │  7  │
├─────┼─────┼─────┼─────┼─────┤
│     │     │     │     │  8  │
└─────┴─────┴─────┴─────┴─────┘

。

---

【正序推导】

通过逆序推导的部分，我们知道每拆掉当前最长的蛇留下的部分可以拼成一个正方形，那么我们可以尝试在边长为 $n$ 的正方形中添加一条长度为 $2n+1$ 的蛇观察其性质。

性质 2：对于任意大小的存在蛇的放置方案，必然沿着右上-左下主对角线对称。

这个用归纳法证明是可以的。$n=1$ 显然成立。$n\gt 1$ 时，假设 $n-1$ 的情况成立，分两种情况讨论：

• 剩余部分是一个边长为 $n-1$ 的正方形（左下或右上），那么加上一条 L 形蛇必然也是对称的。

• 剩余部分两部分可以拼成一个正方形。注意到大小为 $n-1$ 的正方形拆分成两部分也是沿着右上-左下主对角线对称，那么剩余两部分在大小为 $n$ 的正方形里面的体现是一部分包含 $(1,n)$，另一部分包含 $(n,1)$。这两部分显然也是沿着右上-左下主对角线对称的。那么这条长度为 $2n-1$ 的蛇也必然对称。

---

同时，我们可以由对称性，得出一下结论：

性质 3：每条蛇必定穿过右上-左下主对角线恰好一次。

性质 4：所有蛇在每一个右上-左下对角线的相对顺序不变。

那么此时可以根据性质 3 解决 $k=0$ 的子问题了。因为主对角线一旦确定，那么其余对角线的元素也可以一一确定。

问题在于 $k\neq0$ 的情况。我们可以发现每一条偏左上的（$r+c\le n+1$）斜对角线必然形如以下形态：

DDD...DN(New Snake)RRR...R

那么其实本质上是在每一行确定 N 的位置，只要满足 D 全在右边，R 全在左边就行了。每行系数相乘即是答案。