写在前面：难度还没更新，如果看到了难度会及时更新的。

Magical Tiered Cake

来源：CF Round 1101 D

难度：?

汉诺塔问题变形。Ad - hoc。

先考虑什么时候是无解的。当存在 ai≥ia_i\ge i 时，发现第 ii 个盘子无论如何都动不了（因为在它自身能动之前上面永远小于 ii 个盘子）。

特殊情况 ∀i∈[1,n],ai=0\forall i\in[1,n],a_i=0 就是普通的汉诺塔问题。

接下来考虑一般情况，我们希望对于一般情况也能像汉诺塔问题一样递归处理。然后我们可以找到一样的递归动机，即最大的一个盘子移动的目标位置顶上不能有任何比它还大的盘子。那么就考虑最大的一个盘子什么时候是能动的。设此时需要处理有 kk 个盘子的子问题，将所有盘子从 A 地移动到 C 地，B 地可以作为中转点。那么当 ak=0a_k=0 时，照原样汉诺塔问题，即需要把上面的 k−1k-1 个盘子都移动到 B 地才能动第 kk 个盘子。即操作：

solve(k−1,A→B),move(k,A,C),solve(k−1,B→C)solve(k-1,A\to B),move(k,A,C),solve(k-1,B\to C)

。当 ak>0a_k\gt 0 时，有一个比较简单直接的方法就是先把最上面的 k−1−akk-1-a_k 个盘子先移到 B，然后从 A 移第 kk 个盘子到 C，再把 B 的 k−1−akk-1-a_k 个盘子移回 A，最后把还在 A 的 k−1k-1 个盘子移到 C。即操作：

solve(k−1−ak,A→B),move(k,A,C),solve(k−1−ak,B→A),solve(k−1,A→C)solve(k-1-a_k,A\to B),move(k,A,C),solve(k-1-a_k,B\to A),solve(k-1,A\to C)

。不难证明这样的步数一定在 2k2^k 以内。

Snaking Arrangement

来源：CF Round 1101 E

难度：?

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

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

【逆序推导】

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

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

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

，变成：

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

。

【正序推导】

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

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

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

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

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

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

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

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

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

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

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

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