专栏文章

CF1158F Density of subarrays

EErine
CF1158F题解参与者 4已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@miqk9rnc
此快照首次捕获于
2025/12/04 06:11
3 个月前
此快照最后确认于
2025/12/04 06:11
3 个月前
查看原文
第一个独立切的 *3500，写篇题解纪念一下（。虽然感觉没有 *3500 就是。
考虑，现在给你一个序列，怎么算它的密度？如果你去了 THUSC2024 大概会马上想到那个 D1T2，那道题告诉我们序列的密度可以这样简便地刻画：
往一个栈里从前往后依次加入序列的元素，如果某个时刻栈里 [1,c][1,c] 全部出现过，就将密度 +1+1，并清空栈。
那套到这个题上，我们不妨将“清空栈”的操作看做一条在原序列上的分割线。假设我们枚举了原序列中的一些分割线，那么这等价于钦定了子序列满足以下条件：
  • 每个分割线前面一个数，对于这个值，在当前分割线与上一个分割线之间只能选前面这个数，其他的相同值的数都不能选（否则，中间会存在别的分割线）
  • 每个分割线不等于其前面一个数的值，必须在两条分割线间至少出现一次
  • 最后一条分割线后面 [1,c][1,c] 不能都出现过
不难发现分割线之间的贡献是独立的，且等于 ∏c≠u(2cntc−1)\prod_{c\neq u}(2^{cnt_c}-1)，其中 uu 是右侧分割线前面的位置的值。那么可以直接考虑 dp：令 fi,jf_{i,j} 表示最后一条分割线在 i,i+1i,i+1 之间，一共有 jj 条分割线的子序列方案数。注意到预处理逆元之后，[l−1,r][l-1,r] 的转移系数可以由 [l,r][l,r] 的 Θ(1)\Theta(1) 得到，于是我们可以获得 Θ(n3)\Theta(n^3) 的做法。
真的是 Θ(n3)\Theta(n^3) 吗？仔细一点会发现 jj 至多是 ⌊nc⌋\left\lfloor\dfrac nc\right\rfloor，于是复杂度是 Θ(n3c)\Theta\left(\dfrac{n^3}c\right)，至少这告诉我们，cc 较大的时候可以这样做了。
继续研究考虑 cc 比较小的情况，注意到存在 Θ(n2c⋅2c)\Theta\left(\dfrac{n^2}c\cdot 2^c\right) 的暴力 dp：fi,j,Sf_{i,j,S} 表示考虑了前 ii 个数，已经贪心分成了 jj 段，且最后一段还没清空的栈里有 SS 这些元素的子序列数量，可以解决掉 cc 比较小的部分。
于是 c≤12c\le 12 时跑小 dp，c>12c\gt 12 时跑大 dp，我们解决掉了这个题。
关于卡常：注意数组访问连续可以减小极大的常数，以及 #define int long long 会导致代码常数巨大。

评论

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

正在加载评论...