题解：P13694 [CEOI 2025] Splits

· · 题解

纯纯意义不明弱智题，但是严肃被通信正义击杀了。

从 T 中随便拿一个排列 q，考虑设 f_{i,j,k} 表示 q 只考虑 [i,j] 和 [k,n] 的方案数，转移就是拓展 i-1 或者 k-1，然后在其他 T 中元素中这些数对应位置也需要一直维持类似的结构。但是可能出现在某个 T 中的排列中这些数对应的位置糊成了一个区间，你不知道中间有没有分界点，所以要想办法让只有一个区间的情况必定没有分界点。

考虑一个东西：直接爆搜 p，确定一个数的时候，当前确定的数不是某个排列的前缀那就可以立刻确定这个排列的分界点。如果所有分界点都确定了，每个排列分界点后面的数已经被选上了，不会出现上面说的两个区间糊成一坨的情况，上面的 DP 就是可行的了。

而这个爆搜其实只有 O(n^2+nm)，因为你相当于在这些排列构成的 trie 树上 DFS，然后如果当前节点不是所有排列的前缀显然只有最多两种选择。

然后考虑 DP 的部分，考虑什么转移是合法的。对于一个排列，设已有的数对应位置是 S，新加入的数在 x。首先 x-1\notin S，不然就糊成一坨了。然后如果 S 不构成一个区间，那需要 x+1\in S。直接判断能得到 O(n^4m) 之类的复杂度的做法，但是可以无压力通过 sub6。code

剩下的就是怎么优化这个判断了。考虑 bitset 维护出符合条件的排列集合。x-1\notin S 维护一个 s_{i,j} 表示 i 的位置 \le j 的排列个数之类的就行。x+1\in S 维护一个 bs_{i,j} 表示 i 的位置 \ge j 的排列集合，S 是一个区间的情况就枚举一个排列的一个区间，如果它在我们 DP 的那个排列上是 [i,j]\cup[k,n] 的结构就塞进这个状态的 bitset。

时间复杂度 O(\frac{n^3m}w)，常数很小。code