题解：P17783 森井飞鸟不是罪过

· · 题解

我们首先考虑先观察只有数字 1,2,3 的序列，我们不难发现只要 1,2,3 都出现了，这个序列可以任意排序。这启示我们操作的自由度相当高。进一步我们尝试再加入 4，首先我们发现 2 4 1 3 是不可操作的，否则我们考虑，这些 4 会把序列分成若干段。每一段内部如果有 1,2,3，那么根据上面的结论，我们可以先给每一段内部任意排列，然后再和 4 进行操作，最后的结论是，如果不是 2413 这种初始不可操作的情况，并且 1,2,3,4 都出现。序列可以任意排列，具体证明可以先给序列排序，然后操作可逆。

形式化一下上面的推导，我们归纳性地依次加入 1,2,...,n，维护一些极长的，可以内部操作到升序的连续段，每次加入 x 我们看作是加入一个 [x,x]，值为 a_x 的连续段。

我们考虑相邻两个连续段 I_0,I_1，值域分别为 J_0=[l_0,r_0],J_1=[l_1,r_1]（值域显然是一个区间），如果 [l_0,r_0] \cap [l_1,r_1] \ne \varnothing \vee l_0 = r_1+1 \vee l_1 = r_0+1，那么显然可以通过一系列操作把连续段 I_0,I_1 升序排序。证明显然。那么现在我们已经把序列划分为了很多个连续段，不同段之间显然直接在值域上独立，我们可以分开考虑，算完方案之后乘算起来。

现在考虑解决长度为 n 的连续段，值域为 [1,m] 的问题。首先我们记 C_i 代表 i 在段中的出现次数，那么首先一个比较平凡的想法是我们直接把 (c_1,c_2,...,c_m) 这个向量压进状态，设状态 f_S 代表状态为 S 的答案，考虑转移我们做容斥减掉可以把序列划分成若干段的方案，具体来说，我们设一个 g_{S,I} 代表状态 S，最后一个独立段的值域区间为 I 的方案数，那么有转移：

g_{S,I} = \sum_{A+B=S} f_A\times \left([B=0] + \sum_{\text{check}(I,J)=1} g_{B,J}\right) \\ f_S = \frac{(\sum S_i)!}{\prod S_i!} - \sum_{I \subset U} g_{S,I}

这里的 \text{check}(I,J)=1 代表要求 I,J 不能在值域上相交或相邻。

状态总数量是 O(n^2 \times \prod (C_i + 1)) 的，空间复杂度是 O(n^2 2^n) 的，转移直接枚举一个向量 (d_1,d_2,...,d_m)，使得满足 0 \le d_i \le c_i，转移的复杂度是 \sum_{c < C}\prod(c_i+1) = \prod (\sum_{c_i=0}^{C_i}(c_i+1)) = \prod \frac{(C_i+1)(Ci+2)}{2} \le 3^{\sum C_i} = 3^n 的。前后缀优化一下转移，这样得到了一个时间 O(3^n)，空间复杂度 O(n2^n) 的做法，应该可以通过 n\le 18 的数据。

上面的部分应该都是比较平凡的，我们仔细思考一下这个 dp，我们发现大部分 f 的状态都是无用的，因为 f_S 必须要求 S 的所有非 0 位置构成一个连续段，这样可以减少巨量的状态。现在的问题是我们的 g_{S,I} 的状态 S 并不满足这个性质，做一步容斥，下面记 w(S) 代表状态 S 的总方案数（多重集组合数）：

g_{S,I} = \sum_{A +B=S} f_A \times \left(w(B) - \sum_{\text{check}(I,J)=0} g_{B,J}\right)

我们把这三个 dp 数组写成 GF，分别写成 F_I, G_I,W，那么原式形如 G_I = F_IW - F_I \sum G_J，我们给两边同时乘上 W^{-1}，那么也就是 W^{-1}G_I = F_I - F_I \times \sum (W^{-1} G_J)，那么我们只需要算出来 H_I = W^{-1}G_I 即可。这样做的好处是 H_I 的每一个状态，必然都满足非 0 位置是一个区间。我们记 X 为所有元的总和，那么显然有 W = \frac{1}{1-X}，也就是说 W^{-1}G_I = (1-X)G_I。

那么我们记 h_{S,I} = [x^S] H_I，那么我们考虑转移，显然有：

h_{S,I} = [\text{Int}(S) = I]f_S - \sum_{A+B=S} f_A \sum_{\text{check}(I,J)=0} h_{B,J}

这里的 \text{Int}(S) 代表 S 的值域区间。

考虑怎么快速转移，我们把 \text{check}(I,J)=0 的限制容斥一下，处理一下两个数组 \text{pre}_{S,i} 和 \text{suf}_{S,i} 分别代表右端点 \le i 的区间总和和左端点 \ge i 的区间总和。还有一个问题是现在考虑如何快速枚举 A+B=S，我们分成三种情况讨论：A,B 值域不相交，A 某一个值域是原区间，A,B 值域相交。分别枚举这三类即可。对于 A,B 的值域交集，我们直接暴力枚举子向量。

在 n=32 的时候，h_{S,I} 的状态总数大概在 3 \times 10^7 左右。std 没有写变进制编码，用哈希表存状态跑得很慢，卡常后大概跑了 1.5s。