专栏文章

CF1874F Jellyfish and OEIS 题解

ttime_keeper
CF1874F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipr6qe1
此快照首次捕获于
2025/12/03 16:36
3 个月前
此快照最后确认于
2025/12/03 16:36
3 个月前
查看原文

题意

给定一个长度为 nn 的序列 mm。
定义排列的一个区间 [l,r][l,r] 为关键区间，当且仅当 [l,r][l,r] 内的数在这个区间内都出现了一次。也就是关键区间 [l,r][l,r] 是值在 [l,r][l,r] 内的数的排列。
定义一个关键区间 [l,r][l,r] 是合法的，当且仅当 r≤mlr \le m_l。
求有多少长度为 nn 的排列不含有合法关键区间。

题解

题目相当于给定了一些区间，求让这些区间都不是合法关键区间的方案数。
考虑第一层容斥，钦定一个区间集 SS，其内都是关键区间，容斥系数是 (−1)∣S∣(-1)^{|S|}。
一个观察是，如果两个关键区间有交，那么这个关键区间可以被拆分为三个不交关键区间。
设两个关键区间 [l1,r1],[l2,r2][l_1,r_1],[l_2,r_2] 满足 l1<l2≤r1<r2l_1 < l_2 \le r_1 < r_2。
设 [l2,r1][l_2,r_1] 不是关键区间，则其内存在 [l1,l2−1][l_1,l_2 - 1] 内的数或 [r1+1,r2][r_1 + 1,r_2] 内的数。
如果有 [l1,l2−1][l_1,l_2 - 1] 内的数，则 [l2,r2][l_2,r_2] 就不是关键区间。
如果有 [r1+1,r2][r_1 + 1,r_2] 内的数，则 [l1,r1][l_1,r_1] 就不是关键区间。
所以 [l2,r1][l_2,r_1] 是关键区间，易得 [l1,l2−1][l_1,l_2-1] 和 [r1+1,r2][r_1 + 1,r_2] 也是关键区间。
此时钦定的关键区间，要么不交，要么包含。
事实上，这样拆分之后，容斥仍然是对的。
因为原来要求 [l1,r1][l_1,r_1] 和 [l2,r2][l_2,r_2] 合法，已经包含内部 [l1,l2−1],[l2,r1],[r1+1,r2][l_1,l_2 - 1],[l_2,r_1],[r_1 + 1,r_2] 合法，后者可以拼出前者，前者可以拆出后者，要求的是一个东西，方案数是一样的。
设 f(l,r)f(l,r) 表示 [l,r][l,r] 不严格包含关键区间的方案数。
特别的，若 m1=nm_1 = n，答案为 00，否则答案为 f(1,n)f(1,n)。
对于 ff 再套一层容斥。即设 g0/1(l,r,x)g_{0/1}(l,r,x) 表示在 [l,r][l,r] 中包含偶数/奇数个关键区间的方案数。
先考虑严格包含的情况。
g0(l,r,x)=g0(l,r−1,x−1)+∑i=l+1rg1(l,i−1,x)f(i,r)[r≤mi]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≤mi]f(i,r)[r \le m_i] 的意义是不严格包含合法关键区间的方案数。
则 f(l,r)=∑x=1r−l+1(g0(l,r,x)−g1(l,r,x))×x!f(l,r) = \sum_{x=1}^{r-l+1}(g_0(l,r,x) - g_1(l,r,x)) \times x!
xx 个空白可以随便放置，即将 xx 个数安排进 xx 个位置。
然后再把 g0/1g_{0/1} 不严格包含的部分填上。
g1(l,r,x)=g1(l,r,x)+[x=0]f(l,r)[r≤ml]g_1(l,r,x) = g_1(l,r,x) + [x=0]f(l,r)[r \le m_l]
也就是加上了 [l,r][l,r] 是一整个关键区间的方案数。
时间复杂度 O(n4)O(n^4)
如果你被卡常了，可以试试交换数组维度。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...