The 2025 ICPC Asia East Continent Online Contest (II) D题（数学）-北京尧图网络

题目链接奥术巨兽 - 题目 - 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; }

The 2025 ICPC Asia East Continent Online Contest (II) D题（数学）

相关推荐

换季盘点不熬夜：2026零售系统软件哪个好

基于Vue与Three.js的数字孪生可视化系统全栈开发实践

Hyper Pop音乐制作全攻略：从音色设计到混音母带

更多资讯

如何理解和制造buzz：从传播逻辑到实操指南

陪护平台数据看板：核心指标与可视化实践

天梯赛算法竞赛备战：动态规划与图论优化技巧

S32K312基于GPT定时器与EB Tresos实现多任务LED闪烁

锌钢护栏行业趋势与优质厂商评估指南

直流电机H桥驱动选型：压降对比与效率分析

今日更新

淘宝商品详情API开发实战与性能优化指南

Unity Package Manager刷新错误排查与解决方案

Java record 规范构造器能否被反序列化或反射绕过

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？