CF1874F Jellyfish and OEIS 题解

· · 题解

题意

给定一个长度为 n 的序列 m。

定义排列的一个区间 [l,r] 为关键区间，当且仅当 [l,r] 内的数在这个区间内都出现了一次。也就是关键区间 [l,r] 是值在 [l,r] 内的数的排列。

定义一个关键区间 [l,r] 是合法的，当且仅当 r \le m_l。

求有多少长度为 n 的排列不含有合法关键区间。

题解

题目相当于给定了一些区间，求让这些区间都不是合法关键区间的方案数。

考虑第一层容斥，钦定一个区间集 S，其内都是关键区间，容斥系数是 (-1)^{|S|}。

一个观察是，如果两个关键区间有交，那么这个关键区间可以被拆分为三个不交关键区间。

设两个关键区间 [l_1,r_1],[l_2,r_2] 满足 l_1 < l_2 \le r_1 < r_2。

设 [l_2,r_1] 不是关键区间，则其内存在 [l_1,l_2 - 1] 内的数或 [r_1 + 1,r_2] 内的数。

如果有 [l_1,l_2 - 1] 内的数，则 [l_2,r_2] 就不是关键区间。

如果有 [r_1 + 1,r_2] 内的数，则 [l_1,r_1] 就不是关键区间。

所以 [l_2,r_1] 是关键区间，易得 [l_1,l_2-1] 和 [r_1 + 1,r_2] 也是关键区间。

此时钦定的关键区间，要么不交，要么包含。

事实上，这样拆分之后，容斥仍然是对的。

因为原来要求 [l_1,r_1] 和 [l_2,r_2] 合法，已经包含内部 [l_1,l_2 - 1],[l_2,r_1],[r_1 + 1,r_2] 合法，后者可以拼出前者，前者可以拆出后者，要求的是一个东西，方案数是一样的。

设 f(l,r) 表示 [l,r] 不严格包含关键区间的方案数。

特别的，若 m_1 = n，答案为 0，否则答案为 f(1,n)。

对于 f 再套一层容斥。即设 g_{0/1}(l,r,x) 表示在 [l,r] 中包含偶数/奇数个关键区间的方案数。

先考虑严格包含的情况。

g_0(l,r,x) = g_0(l,r - 1,x - 1) + \sum_{i = l+1}^r g_1(l,i - 1,x)f(i,r)[r \le m_i]

这里的 f(i,r)[r \le m_i] 的意义是不严格包含合法关键区间的方案数。

则

f(l,r) = \sum_{x=1}^{r-l+1}(g_0(l,r,x) - g_1(l,r,x)) \times x! 然后再把 $g_{0/1}$ 不严格包含的部分填上。 $g_1(l,r,x) = g_1(l,r,x) + [x=0]f(l,r)[r \le m_l]

也就是加上了 [l,r] 是一整个关键区间的方案数。

时间复杂度 O(n^4)

如果你被卡常了，可以试试交换数组维度。