T1
考虑二分，然后怎么 check。
我们随便选一个点开始 BFS 地移动，如果以它为左上角的正方形可以覆盖整个局面中的所有空格子，那么整个边长就是可行的。
容易证明随便选一个点开始是正确的。
T2
抽象题。
看到数据范围容易有一个状压状物，然而 \(2^n\) 怎么都去不掉。根据某年 NOI 或 WC 的启发，这题可能是个五方到六方的多项式做法。
然后容易想到第一问会做第二问就会了，因为可以逐位尝试确定。可以做到在第一问的复杂度上乘一个 \(\mathcal O(n^2)\)。
然后我就不会了，傻逼吧。
考虑刻画重排排列。
这个东西放到置换环上没有较好的性质，我们考虑另一种方式。
一个排列可以与一个 \([1,n]\to [1',n']\) 的完美匹配相对应。左边是位置，右边是值。一个 \(p_i\) 可以看成一条边，如果我们把大的那个看成右部点，小的那个看成左部点，那么卦象就是所有右部点的和减去所有左部点的和。由于左右部点总和是确定的，所以知道其中一个就能知道另一个。
所以如果我们知道了左部点和为 \(k\) 的方案数，我们就能知道卦象为 \(n\times (n+1)-2k\) 的方案数。
然后考虑计数匹配。我们考虑每个数可以选择左部还是右部，也可以选择是否和前面的某个数匹配。为了方便维护一方的和，我们钦定类似 \((1,1',2,2',\cdots,n,n')\) 这样转移，这样我们新加的点要么匹配要么就必然是左部点。
转移顺序是为了方便计量一些东西而服务的。
于是 dp 很显然了。\(dp_{i,j,k}\) 表示前 \(i\) 的前缀，还有 \(j\) 个左部点没匹配，左部点的和是 \(k\)。状态数 \(\mathcal O(n^4)\)，转移 \(\mathcal O(1)\)。
第二问用 \(\mathcal O(n^6)\) 卡常可以轻易通过。
标签：Qingbai,匹配,Cup,可以,户厕,左部点,mathcal,考虑,我们 From： https://www.cnblogs.com/lemonniforever/p/18369855