题目链接奥术巨兽 - 题目 - QOJ.ac题目大意给定一个数组可以选择该数组的任意非空子序列当该子序列出售一个元素时其他元素可以加上失去元素的值一个子序列的价值定义为如果以最优的顺序售出该子序列中的其他巨兽最后剩下的一只巨兽所能达到的最大攻击力。计算该序列所有非空子序列的价值之和。请将结果模 998244353 后输出。题目思路对于子序列只有2个元素时例1子序列 [1, 2]取最大 2 → [12] [3]价值 3 1 2例2子序列 [1, 3]取最大 3 → [13] [4]价值 4 1 3例3子序列 [2, 3]取最大 3 → [23] [5]价值 5 2 3结论1对于长度为 2 的子序列[a, b]a ≤ b价值 a b对于子序列元素大于2个时例4子序列 [1, 2, 3]取最大 3 → [13, 23] [4, 5]取最大 5 → [45] [9]价值 9 1 2 2×3例5子序列 [1, 4, 6]取最大 6 → [16, 46] [7, 10]取最大 10 → [710] [17]价值 17 1 4 2×6例6子序列 [1, 2, 3, 4]取最大 4 → [14, 24, 34] [5, 6, 7]取最大 7 → [57, 67] [12, 13]取最大 13 → [1213] [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]在这个子序列中是第t1小根据公式如果A[i]是第 1 小t0系数 1如果A[i]是第 2 小t1系数 1如果A[i]是第j小j ≥ 3即 t ≥ 2系数 2^(j-2) 2^(t-1)后面元素的选择不管前面选多少个后面的N-1-i个元素都可以任意选择方案数为2^(N-1-i)前面元素的选择: 从i个元素里面选t个0ti),也就是C(i,t)作为第1小t0方案数 C(i, 0) × 2^(N-1-i) 2^(N-1-i)贡献 A[i] × 2^(N-1-i)作为第2小t1方案数 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) × Σ_{t2}^i C(i, t) × 2^(t-1)通过二项式定理(a b)^i Σ_{t0}^i C(i, t) × a^(i-t) × b^t令 a1, b2(1 2)^i Σ_{t0}^i C(i, t) × 1^(i-t) × 2^t3^i Σ_{t0}^i C(i, t) × 2^t即Σ_{t0}^i C(i, t) × 2^t 3^i所以Σ_{t2}^i C(i, t) × 2^t 3^i - 1 - 2i因为Σ_{t2}^i C(i, t) × 2^t (Σ_{t0}^i C(i, t) × 2^t) - C(i,0)×2^0 - C(i,1)×2^1 (Σ_{t0}^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; }