题目链接：奥术巨兽 – 题目 – QOJ.ac
题目大意：给定一个数组，可以选择该数组的任意非空子序列，当该子序列出售一个元素时，其他元素可以加上失去元素的值，一个子序列的价值定义为：如果以最优的顺序售出该子序列中的其他巨兽，最后剩下的一只巨兽所能达到的最大攻击力。计算该序列所有非空子序列的价值之和。请将结果模 998244353 后输出。
题目思路：
对于子序列只有2个元素时：
例1：子序列 [1, 2]
-
取最大 2 → [1+2] = [3]
-
价值 = 3 = 1 + 2
例2：子序列 [1, 3]
-
取最大 3 → [1+3] = [4]
-
价值 = 4 = 1 + 3
例3：子序列 [2, 3]
-
取最大 3 → [2+3] = [5]
-
价值 = 5 = 2 + 3
结论1：对于长度为 2 的子序列 [a, b]（a ≤ b），价值 = a + b
对于子序列元素大于2个时：
例4：子序列 [1, 2, 3]
-
取最大 3 → [1+3, 2+3] = [4, 5]
-
取最大 5 → [4+5] = [9]
-
价值 = 9 = 1 + 2 + 2×3
例5：子序列 [1, 4, 6]
-
取最大 6 → [1+6, 4+6] = [7, 10]
-
取最大 10 → [7+10] = [17]
-
价值 = 17 = 1 + 4 + 2×6
例6：子序列 [1, 2, 3, 4]
-
取最大 4 → [1+4, 2+4, 3+4] = [5, 6, 7]
-
取最大 7 → [5+7, 6+7] = [12, 13]
-
取最大 13 → [12+13] = [25]
-
价值 = 25 = 1 + 2 + 2×3 + 4×4
一般规律
对于升序排列的子序列 [a₁, a₂, a₃, …, aₖ]（a₁ ≤ a₂ ≤ … ≤ aₖ），其价值为：
价值 = a₁ + a₂ + 2×a₃ + 4×a₄ + 8×a₅ + … + 2^(k-2)×aₖ
虽然现在有计算每个子序列价值的公式了，但是枚举每个子序列显然是会超时的，那么我们可以使用贡献法：
对数组排序后，考虑位置 i 的元素 A[i]，它前面有 i 个比它小的元素，后面有 N-1-i 个比它大的元素。
对于包含 A[i] 的子序列：
-
从前面 i 个元素中选 t 个（0 ≤ t ≤ i）
-
从后面 N-1-i 个元素中任选（每个可选可不选）
-
那么 A[i] 在这个子序列中是第 t+1 小
根据公式：
-
如果 A[i] 是第 1 小（t=0）：系数 = 1
-
如果 A[i] 是第 2 小（t=1）：系数 = 1
-
如果 A[i] 是第 j 小（j ≥ 3，即 t ≥ 2）：系数 = 2^(j-2) = 2^(t-1)
后面元素的选择：不管前面选多少个，后面的 N-1-i 个元素都可以任意选择，方案数为 2^(N-1-i)
前面元素的选择: 从i个元素里面选t个（0<=t<=i),也就是C(i,t)
作为第1小（t=0）：
方案数 = C(i, 0) × 2^(N-1-i) = 2^(N-1-i) 贡献 = A[i] × 2^(N-1-i)
作为第2小（t=1）：
方案数 = C(i, 1) × 2^(N-1-i) = i × 2^(N-1-i) 贡献 = A[i] × i × 2^(N-1-i)
作为第 j≥3 小（t≥2）：
方案数 = C(i, t) × 2^(N-1-i) 系数 = 2^(t-1) 贡献 = A[i] × 2^(N-1-i) × C(i, t) × 2^(t-1)
对所有 t ≥ 2 求和：
贡献 = A[i] × 2^(N-1-i) × Σ_{t=2}^i C(i, t) × 2^(t-1)通过二项式定理(a + b)^i = Σ_{t=0}^i C(i, t) × a^(i-t) × b^t，令 a=1, b=2：
(1 + 2)^i = Σ_{t=0}^i C(i, t) × 1^(i-t) × 2^t 3^i = Σ_{t=0}^i C(i, t) × 2^t即Σ_{t=0}^i C(i, t) × 2^t = 3^i
所以Σ_{t=2}^i C(i, t) × 2^t = 3^i – 1 – 2i，因为Σ_{t=2}^i C(i, t) × 2^t = (Σ_{t=0}^i C(i, t) × 2^t) – C(i,0)×2^0 – C(i,1)×2^1 = (Σ_{t=0}^i C(i, t) × 2^t) – 1 – 2i
最后化简得S = (1/2) × (3^i – 1 – 2i)，那么位置i的总贡献=
A[i] × 2^(N-1-i) × [1 + i + (3^i – 1 – 2i)/2] (当 i ≥ 2)
对于 i < 2，需要单独处理：
-
i = 0：贡献 = A[0] × 2^(N-1)（只能作为第1小）
-
i = 1：贡献 = A[1] × [2^(N-2) + 1×2^(N-2)] = A[1] × 2^(N-1)（作为第1小和第2小）
接着遍历剩余位置求和即可
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 9;
using ll = long long;
const ll MOD = 998244353;
ll a[MAXN];
// 快速幂：计算 a^b % MOD
ll ksm(ll a, ll b)
{
ll res = 1;
while (b > 0)
{
if (b & 1)
res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
// 求逆元：inv(b) = b^(MOD-2) % MOD
ll inv(ll b)
{
return ksm(b, MOD – 2);
}
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
sort(a + 1, a + 1 + n);
ll ans = 0;
ll inv2 = inv(2); // 2 的逆元
for (int i = 1; i <= n; i++)
{
ll coef; // 贡献系数
if (i == 1)
{
// 位置 1：只能作为第1小
// 贡献 = a[1] × 2^(n-1)
coef = ksm(2, n – 1);
}
else if (i == 2)
{
// 位置 2：可以作为第1小或第2小
// 贡献 = a[2] × [2^(n-2) + 1×2^(n-2)] = a[2] × 2^(n-1)
coef = ksm(2, n – 1);
}
else
{
// 位置 i >= 3：
// 贡献系数 = 2^(n-i) × [1 + (i-1) + sum3[i-1]]
// 其中 sum3[i-1] = (3^(i-1) – 1 – 2(i-1)) / 2
// 计算 3^(i-1)
ll pow3 = ksm(3, i – 1);
// 计算 sum3 = (3^(i-1) – 1 – 2(i-1)) / 2
ll sum3 = (pow3 – 1 – 2LL * (i – 1)) % MOD;
if (sum3 < 0)
sum3 += MOD;
sum3 = sum3 * inv2 % MOD; // 除以 2
// 计算 2^(n-i)
ll pow2 = ksm(2, n – i);
// 系数 = 2^(n-i) × [1 + (i-1) + sum3]
ll part = (1 + (i – 1) + sum3) % MOD;
coef = part * pow2 % MOD;
}
ans = (ans + coef * a[i]) % MOD;
}
cout << ans << "\\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t–)
{
solve();
}
return 0;
}
