Products of Min-Max

题意

長さ $N$ の整数列 $A$ が与えられます。$A$ の空でない部分列 $B$ は $2^N−1$ 個あります。これらについて $\max(B)×\min(B)$ の値を計算し、その総和を答えてください。

ただし、答えは非常に大きくなる場合があるので、$998244353$ で割った余りを答えてください。

解析

首先，答案与 $A$ 中各数的位置无关，为了方便处理，我们可以先离散化，获得各个值在 $A$ 中出现的次数。记从小到大的第 $i$ 个在 $A$ 中出现过的值为 $V_i$，出现次数为 $C_i$。

从小到大处理这些值。设 $\text{sum}$ 为不包含 $V_1\sim V_{i-1}$ 以外所有数的所有子序列 $B$ 的 $\min(B)$ 的和，则在处理第 $i$ 个值 $V_i$ 时：

• 包含且只包含 $V_i$ 的子序列个数为 $2^{C_i}-1$。这些子序列和 $\text{sum}$ 代表的子序列组合，可以产生 $\text{sum}\times V_i$ 的贡献
• 之后，将包含 $V_i$，且不含 $V_1\sim V_{i-1}$ 的所有子序列的最小值的和计入 $\text{sum}$，即 $\text{sum}\gets 2^{C_i}\times\text{sum}+V_i(2^{C_i}-1)$

实现

#include <bits/stdc++.h>

typedef long long int ll;
const int maxn = 2e5 + 19, mod = 998244353;

int n, a[maxn], tmp[maxn], tot, cnt[maxn], ans, sum;

int main(){
    std::scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        std::scanf("%d", a + i), tmp[i] = a[i];
    std::sort(tmp + 1, tmp + 1 + n), tot = std::unique(tmp + 1, tmp + 1 + n) - tmp - 1;
    for(int i = 1; i <= n; ++i)
        ++cnt[std::lower_bound(tmp + 1, tmp + 1 + tot, a[i]) - tmp];
    static int p2[maxn]; p2[0] = 1;
    for(int i = 1; i <= n; ++i) p2[i] = 2 * p2[i - 1] % mod;
    for(int i = 1; i <= tot; ++i){
        ans = (ans + (ll)(p2[cnt[i]] - 1) * tmp[i] % mod * (sum + tmp[i])) % mod;
        sum = ((ll)sum * p2[cnt[i]] + (ll)tmp[i] * (p2[cnt[i]] - 1)) % mod;
    }
    std::printf("%d\n", (ans + mod) % mod);
}

来源

AtCoder Regular Contest 116 B - Products of Min-Max

评论

Gitalking ...