自动搬运

查看原文

来自洛谷，原作者为

	chenzida ACM加油，冲wf

搬运于2025-08-24 22:06:49，当前版本为作者最后更新于2021-02-14 05:06:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人， 人人本着正义之名，长存不灭的过去、逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。————世界上最幸福的女孩

珂朵莉，要一直幸福哦。

第一道珂朵莉相关 $\text{Ynoi}$ 祭。

这题的难点首先在读题。。。去重是对于每一个子序列分别去重，比如 $1,2,4,2,2$ 去重之后是 $1,2,4$。而不是有两个子序列完全相同时去掉其中一个。

然后读完这个题之后我们发现，如果是有重复的就消去只剩一个，那么每个数在一个子序列中只会出现一次。假设在一个长度为 $t$ 的序列中，数字 $x$ 出现了 $k$ 次，那么它的贡献就是 $(2^t-2^{n-k})x$。

这个式子的证明就是容斥，整体减不合法。如果不选数 $x$ 的话就是剩下 $t-k$ 个随便选，也就是 $2^{t-k}$。

将这个式子推出来之后我就想直接莫队了，却忽略了一个最大难点，那就是随着区间的移动，我们的区间长度是在不断改变的，也就是 $t$ 其实是不确定的。

所以我们必须将所有贡献以一种形式存储下来，以便莫队移动区间后改变 $t$ 之后使用。

考虑一个在 $\text{Ynoi}$ 中常见的思路，根号分治。

当出现次数 $\leq \sqrt n$ 次的时候，我们出现记录次数，并且记录出现这个次数的数的和。由于乘法结合律，所以我们将这些数绑在一起乘是没有问题的。

当出现次数 $> \sqrt n$ 次的时候，我们记录数，并且直接用 $cnt$ 数组来查看次数。

大体思路明确了，剩下几个小问题

我们的时间复杂度是 $n\sqrt n$ 的，但是如果一不小心就会退化成 $n\sqrt n\log n$。

对于这个问题我们有两个东西要重点说一下。

1.维护出现次数 $> \sqrt n$ 的数，我们发现，在这若干种数中，只有不到 $\sqrt n$ 个数出现次数有可能 $>\sqrt n$。所以我们考虑先预处理一下，将所有在整个序列中出现次数 $>\sqrt n$ 的数都处理出来。也就是说，我不管这个数实际出现几次，我只管它的“天赋”，也就是最多出现的次数会不会超过 $\sqrt n$。如果会的话，我就直接通过 $cnt$ 处理。时间复杂度还是 $n\sqrt n$。

2.快速查询 $2^t$ 的方法。这个方法很明显不能用快速幂，否则时间复杂度会退化。分析复杂度发现，我们可以容忍的最大复杂度是预处理 $O(\sqrt n)$，查询 $O(1)$。比起查询的 $O(1)$，我们发现预处理的时间较为宽裕，所以我们考虑光速幂，即预处理出来 $2^0,2^1...,2^{\sqrt n-1}$ 以及 $2^{\sqrt n},2^{2\sqrt n}...2^{\sqrt n\times \sqrt n}$。然后 $O(1)$ 组合相乘查询即可。

注意其中的 $\sqrt n$ 均表示 $n$ 的算术平方根下取整。

然后这题也没啥细节了，反正我是用了很短的时间一遍就过了。