题解 CF1158F【Density of subarrays】

· · 题解

神题。

首先，我们不妨从简单的情形下手：如何求出一个序列的 p 值（此处的 p 即题面中的 p）？

只需要每次删掉该序列最短的出现了所有元素的前缀，计算删除次数即可。

于是这促使我们想出一个DP：设 f_{i,j} 表示从位置 i 开始的后缀中，删除次数恰为 j 的子序列共有多少个。为了避免重复计算，我们强制令 子序列中必须包含位置 i 的元素。

考虑枚举上述删除的前缀的终点，设其为 j。则我们需要知道区间 [i,j] 中，有多少个子序列同时包含了位置 i 与 j，且位置 j 的元素仅在该序列中出现一次。

这个可以预处理出来。设 g_{[i,j]} 为上述子序列数量。则我们可以固定 i，然后用桶维护随着 j 的增加每个元素出现的次数。

如果每种元素都出现了，且 a_j 只出现了一次的话，设 cnt_i 为元素 i 出现的次数，则 g_{[i,j]}=2^{cnt_{a_i}-1}\prod\limits_{k\neq a_i,k\neq a_j}(2^{cnt_k}-1)，因为 a_j 出现的位置是确定的（只能在位置 j 出现一次 ）；a_i 已经确定在位置 i 出现一次，故剩下的位置可以任意出现与否；其余的东西不能一个都不出现。

同时，我们还能同时求出每个 f_{i,0}，作为DP的起始值。要分为后缀 [i,n] 中有无出现全部元素进行计算：若无出现，则就是 2^{n-l}，因为除了 a_i 强制出现以外，其它东西无论出不出都是合法的；若有出现，就从总方案数 2^{n-l} 中减去每种都出现了至少一次的方案即可。

明显，通过 g_{[i,j]} 可以 O(1) 推出 g_{[i,j+1]}，因此 g 数组可以 O(n^2) 计算。

考虑先列出DP转移式：f_{i,j}=\sum\limits_{k=i}^ng_{i,k}\sum\limits_{l=k+1}^{n+1}f_{l,j-1}，边界值为所有之前求出的 f_{i,0}，并且我们令 f_{n+1,0}=1。

这个复杂度是 O(n^4) 的；但是我们可以通过令 s_{i,j} 表示 f 的后缀和来做到 O(n^3)。

于是现在转移式就是 f_{i,j}=\sum\limits_{k=i}^ng_{i,k}s_{k+1,j-1}。

怎么优化？

我们想到一个最naive的优化方式：任意子序列，其 p 的最大值只能为 \left\lfloor\dfrac{n}{c}\right\rfloor。于是我们可以只将 j 一维枚举到 \left\lfloor\dfrac{n}{c}\right\rfloor 即可。

于是复杂度变为 \dfrac{n^3}{c}，通过大力卡常可以处理 c>10 的情形。

但是，当 c\leq 10 时，因为 c 很小，可以考虑状压：设 f_{i,j,k} 表示前缀 i，分了 j 段，剩下最后一段中元素的出现状态是 k。如果转移到 k 满的状态，就转而转移到 k 空的状态，且 j 增加 1。

明显此部分复杂度为 \dfrac{n^22^c}{c}，能够处理 c\leq 10 的情形。

为什么这个边界恰恰是 10 呢？因为 10 是 \log n，也是状压复杂度超过暴力的界点。

于是，取 c=\log n，复杂度为 O(\dfrac{n^3}{\log n})。

但是，就算这样，还需要大力卡常。

下面介绍两个配合使用的卡常技巧：

  1. 因为模数是 998244353，所以开 long long 存DP数组，就可以每 8 次加法再模一次，这样子就使得取模常数变成了 \dfrac{1}{8}。

  2. 如果实在卡不过去了（比如说我很丑的代码），可以在CF上开 GNU C++17 (64) 这门语言，它会大幅提升 long long 的常数，因而放过我的代码。但是副作用是，因为在洛谷上没法选这个语言，所以在洛谷上就过不去，只能在“尝试过的题”中吃灰了。

（同时，悄悄说一句，这个语言还支持 __int128 哦！只不过对我们这题没啥用就罢了）

因为是压时限过的，不保证第二次再交还能过，这里就直接贴链接了：

代码戳这儿