题解AT_agc067_d【Unique Matching】

· · 题解

Upd

竟然自己做出来了 3300+，早知道就打这场 AGC 的，但也想了很久，而且想到之前也很绝望，C 看了也没思路，完全猜不到结论。真是赛时也不一定会看这道题并坚持想。过 AD 的表现分也就 3300 那样，也没比之后那场 ARC 高太多，就这样吧。

不知道该叫啥的链接

思路跟官方题解在第二步就分道扬镳。

第一步的转换是一样的这步真的会有不一样的吗，就是由于匹配方式唯一，所以直接认为匹配是 x_i = i，之后给答案乘上 n! 即可。

那么怎么确定答案是否唯一呢？行列式？不太行，因为方案不唯一不代表行列式一定为 0，有反例 \{[1,2],[1,3],[2,3]\}，之前在某次模拟赛的时候猜过这个结论但发现了问题并想出了正解，但那次直接把这个假做法放过去了，火大。

考虑如果给定了这些区间一般会怎么判定，首先一定存在长度为 1 的区间，否则答案一定不唯一。然后给这些长度为 1 的位置直接分配，之后不断产生新的只包含一个没有确定值的位置的区间再进行分配，只有用这种方式可以分配完所有区间匹配才唯一。

这个过程看上去很可 DP，但似乎不太可转移。从前往后枚举确定的位置似乎不太可行，因为此时的限制是它可以覆盖它周围的之前被选过的位置，这样就要把这些全部计入状态，没啥前途。

但反过来考虑最后被确定的倒很可行，这时的限制是之后（操作的之前）的所有区间都不能覆盖它，因为那时它都没有值，那么整个序列就在它这里劈开了，并且这个最后区间可以任意覆盖宁教我覆天下人，休教天下人覆我（雾）。天啊，简直就是个完美的转移模型！

但不用想都知道这样会算重，因为这本质就是个拓扑序，而能放在最后的点会有很多，这时考虑经典的子集容斥转移应该能做并优化到正解复杂度，写题解的时候想了一下，但我没那么做（？），留给读者自行拓展。

考虑怎么做到只转移编号最小的可转移位置，设它为 p。那么考虑它时最小的位置说明什么，说明任意一个小于 p 的位置都不能转移（？），也就是被一个除自己外的区间覆盖，而 [l_p,p) 已经被 p 覆盖了，所以只需要保证 [1,l_p) 被覆盖即可。

那么考虑将这个限制也加入状态，记 f_{i,j} 表示共有 i 个位置，并且最左边的 j 个被限制必须被一个其他的区间覆盖的方案数，答案即 f_{n,0}。

转移考虑枚举 p 与 l_p，显然 p 只能在右边的 i-j 个里，下面进行分讨：

神奇，两种情况的结果一样，求出右边的情况后可以写出转移式，边界即 f_{0,0}=1：

f_{i,j} = \sum\limits_{p = j+1}^i \sum\limits_{l_p = 1}^p f_{p-1,l_p-1}f_{i-p,0}(i-p+1)

稍微整理一下，把变量名改的好看点（？）：

f_{i,j} = \sum\limits_{k = j}^{i-1} \sum\limits_{l = 0}^{k-1} f_{k,l}f_{i-k-1,0}(i-k)

写出来，发现答案对了，那么考虑优化。

看一眼这个式子就知道，里面 l 的枚举没啥意义，因为只涉及一个变量，直接设 g_i = \sum\limits_{j=0}^{j=i-1} f_{i,j}，那么变成：

f_{i,j} = \sum\limits_{k = j}^{i-1} g_kf_{i-k-1,0}(i-k)

然后仔细观察发现这像是个后缀和的样子，于是可以优化为：

f_{i,j} = f_{i,j+1} + g_jf_{i-j-1,0}(i-j)

同时处理 g，做到 O(n^2)，代码，代码中的 dp_{i,j} = f_{i+j,i}，一开始是这么推的，但发现改成题解里的那样更简洁。