MoonLight的运算问题【牛客tracker 每日一题】

MoonLight的运算问题算法题目时间限制1秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述月色哥哥手中有一个数字x xx最初x 0 x 0x0。给出一个长度为n nn的序列a aa月色哥哥会从序列的第一个元素a 1 a_1a1​按顺序看到序列的最后一个元素a n a_nan​。对于序列的第i ii个元素a i a_iai​月色哥哥可以进行下面的操作之一令x x ⋅ a i x x \cdot a_ixx⋅ai​令x x a i x x a_ixxai​。请求出x xx的最大值并输出这个最大值除998244353 998244353998244353的余数。输入描述第一行包含一个整数T ( 1 ≤ T ≤ 10 5 ) T(1 \le T \le 10^5)T(1≤T≤105)表示测试用例的组数。对于每组测试用例第一行包含一个整数n ( 1 ≤ n ≤ 2 ⋅ 10 5 ) n(1 \le n \le 2\cdot 10^5)n(1≤n≤2⋅105)表示序列的长度。第二行包含n nn个整数a 1 … a n ( 0 ≤ a i ≤ 10 9 ) a_1 \dots a_n(0 \le a_i \le 10^9)a1​…an​(0≤ai​≤109)表示该序列。保证对于所有的测试用例n nn的总和不超过2 ⋅ 10 5 2 \cdot 10^52⋅105。输出描述对于每组测试用例仅输出一行包含一个整数表示答案。样例输入3 2 1 1 1 0 1 998244353样例输出2 0 0样例解释第一组样例初始x 0 x 0x0第一个元素a 1 1 a_11a1​10 1 1 0110110 × 1 0 0 \times 100×10选加法x 1 x1x1第二个元素a 2 1 a_21a2​11 1 2 1121121 × 1 1 1 \times 111×11选加法最终最大值为2。第二组样例初始x 0 x 0x0元素为00 0 0 0000000 × 0 0 0 \times 000×00结果0。第三组样例998244353 998244353998244353模998244353 998244353998244353等于0。解题提示拓展初始值x 0 x 0x0注意当x 0 x 0x0时乘任何数结果依旧是0优先选加法当a i 0 a_i 0ai​0加法得到x 0 x x0xx0x乘法得到0只要当前x 0 x0x0一定选加法当a i 1 a_i1ai​1x 1 x × 1 x1 x \times1x1x×1永远选加法其余情况比较x a i xa_ixai​和x × a i x \times a_ix×ai​取较大值运算之后再对998244353 998244353998244353取模。⚠️注意不能中途直接取模比较大小模运算会破坏数值大小关系需要保留真实数值逻辑判断选加还是选乘运算完成后再取模。解题思路本题是贪心 模运算的在线决策问题。初始值x 0 x0x0按顺序处理每个a i a_iai​每次可选择加或乘求最终x xx的最大值对998244353 998244353998244353取模的结果。由于x xx的真实值可能极大无法直接存储但可以利用“x xx与1 11的大小关系”来决策同时用模运算维护结果避免溢出。1. 问题等价转化当前值x xx与1 11的关系每次操作前x xx的真实值对后续决策影响很大若x ≤ 1 x \le 1x≤1则对于任意a i ≥ 0 a_i \ge 0ai​≥0都有x a i ≥ x × a i x a_i \ge x \times a_ixai​≥x×ai​等号当x 0 , a i 0 x0,a_i0x0,ai​0或x 1 , a i 0 x1,a_i0x1,ai​0时取得。因此此时加法永远不劣于乘法应选择加法。若x 1 x 1x1当a i ≥ 2 a_i \ge 2ai​≥2时x × a i ≥ x a i x \times a_i \ge x a_ix×ai​≥xai​因为x a i − ( x a i ) ( x − 1 ) ( a i − 1 ) − 1 ≥ 0 x a_i - (x a_i) (x-1)(a_i-1)-1 \ge 0xai​−(xai​)(x−1)(ai​−1)−1≥0当x 2 , a i 2 x2,a_i2x2,ai​2时取等号其余均大于。所以乘法不劣于加法。当a i ≤ 1 a_i \le 1ai​≤1时x a i x × a i x a_i x \times a_ixai​x×ai​a i 0 a_i0ai​0或1 11时乘法至多等于x xx而加法更大。因此应选择加法。关键性质一旦真实值x xx超过1 11它永远不会再降回≤ 1 \le 1≤1因为加法不减小乘法也不减小。所以决策规则可以简单固定。2. 算法实现为了在不存储真实值的情况下做出正确决策使用一个变量s来跟踪真实值是否已经超过1 11初始化x_mod 0, flag 0。其中flag表示真实值是否 1 11用s表示当前真实值当它≤ 1 \le1≤1时否则只记录s2作为标记。遍历每个a i a_iai​若flag 0真实值≤ 1 \le1≤1选择加法s a_ix_mod (x_mod a_i) % MOD。若s 1则之后进入flag 1状态。否则真实值 1 11若a i ≥ 2 a_i \ge 2ai​≥2选择乘法x_mod x_mod * a_i % MOD若a i ≤ 1 a_i \le 1ai​≤1选择加法x_mod (x_mod a_i) % MOD。最后输出x_mod。为什么s不会溢出s只在flag0时更新此时s初始为0 00每次加a i a_iai​但一旦s 1就停止更新因此s最大不超过2 max ⁡ ( a i ) ≤ 10 9 2 2 \max(a_i) \le 10^922max(ai​)≤1092远小于long long上限不会溢出。之后s不再变化只作为标志使用。3. 复杂度分析时间复杂度每组数据遍历一次序列O ( n ) O(n)O(n)。所有测试数据∑ n ≤ 2 × 10 5 \sum n \le 2\times 10^5∑n≤2×105总时间O ( ∑ n ) O(\sum n)O(∑n)非常快。空间复杂度O ( n ) O(n)O(n)存储序列或可优化为O ( 1 ) O(1)O(1)边读边处理但给定实现使用vector仍为O ( n ) O(n)O(n)在限制内可行。总结利用“真实值是否超过1 11”作为决策分界线通过一个不溢出的标志变量避免直接比较巨大整数同时在模意义下维护答案。贪心策略正确性由简单的代数不等式保证实现简洁高效。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod998244353;llmx(vectorlla){ll x0,s0;for(autop:a){if(s1){sp;x(xp)%mod;}else{if(p2)x(x*p)%mod;elsex(xp)%mod;}}returnx;}voidsol(){ll t;cint;while(t--){ll n;cinn;vectorlla(n);for(ll i0;in;i)cina[i];coutmx(a)\n;}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);sol();return0;}