首页 > 极客资料博客日记

题解：AT_arc116_b [ARC116B] Products of Min-Max

2024-09-08 22:00:06极客资料围观24次

极客之家推荐题解：AT_arc116_b [ARC116B] Products of Min-Max这篇文章给大家，欢迎收藏极客之家享受知识的乐趣

在题库里面乱翻，就翻到了。

因为在这道题里面子序列不需要考虑元素顺序，所以原序列无论是什么顺序都不会影响答案。

所以先把元素按照从大到小的顺序排列，然后考虑每个元素的贡献。

在当前序列中，对于元素 \(a_i\)，不妨设其为最小值，并去寻找它能作为哪些序列的最小值。容易发现它作为最小值的时候只能和 \(1\sim i\) 中的元素产生贡献。

具体的，对于当前从 \(1\sim i\) 中选择的 \(a_j\)，如果令其为最大值，那么由 \(a_i\) 和 \(a_j\) 这两个值作为最值的序列元素一定都在 \(j\sim i\) 之间，学过集合的同学都知道，这样的序列显然有 \(2^{i-j-1}\) 个。

这样我们就可以得到一个 \(\mathcal{O}(n^2)\) 的解法，如下：

\[\sum_{i=1}^{n}(a_i\times(\sum_{j=1}^{i}(a_j\times 2^{i-j-1}))) \]

由于 \(i-j-1\) 中会出现负数，我们稍微变一下式子可以得到：

\[\sum_{i=1}^{n}(a_i\times(\sum_{j=1}^{i-1}(a_j\times 2^{i-j-1})+a_i)) \]

但是这样显然还不够，于是我们可以
对 \(j\) 的枚举进行优化。容易想到预处理。

我们用一个中间变量 \(sum\) 表示第二个括号里面的值。每次计算过答案以后，我们让 \(sum\gets sum\times 2+a_i\) 即可。

记得取模。

标签：