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