打卡信奥刷题（3299）用C++实现信奥题 P9049 [PA 2021] Mopadulo 题解

P9049 [PA 2021] Mopadulo题目描述给定一个长度为nnn的序列aaa求有多少种方案可以将aaa划分成若干个区间使得每段区间所有数的和模109710^9 71097的结果为偶数。由于结果可能很大你只需要求出结果对109710^9 71097取模的值。输入格式第一行一个整数nnn第二行nnn个整数a1,a2,⋯ ,ana_1, a_2, \cdots, a_na1​,a2​,⋯,an​。输出格式一行一个整数表示所求的值。输入输出样例 #1输入 #14 1000000006 1 5 1000000004输出 #13说明/提示样例 #1 解释三种划分方式如下[1,4][1, 4][1,4][1,2],[3,4][1, 2], [3, 4][1,2],[3,4][1],[2,3],[4][1], [2, 3], [4][1],[2,3],[4]数据范围对于100%100\%100%的数据1≤n≤3×1051 \leq n \leq 3 \times 10^51≤n≤3×1050≤ai10970 \leq a_i 10^9 70≤ai​1097。C实现#includebits/stdc.husingnamespacestd;constintN3e55,mod1e97;intn,m,a[N],sum[N],lsh[N],f[N];inlineintmod_add(intx,inty){xy;returnxmod?x-mod:x;}structBIT{intc[N];inlinevoidmodify(intx,intk){while(xm){c[x]mod_add(c[x],k);x(x-x);}}inlineintquery(intx){intres0;while(x){resmod_add(res,c[x]);x-(x-x);}returnres;}}odd,even;signedmain(){cin.tie(nullptr)-sync_with_stdio(false);cinn;for(inti1;in;i)cina[i];for(inti1;in;i)sum[i]mod_add(sum[i-1],a[i]);for(inti1;in;i)lsh[m]sum[i];lsh[m]0;sort(lsh1,lshm1);munique(lsh1,lshm1)-lsh-1;even.modify(1,1);for(inti1;in;i){intposlower_bound(lsh1,lshm1,sum[i])-lsh;if(sum[i]1){f[i]mod_add(odd.query(pos),mod_add(even.query(m),mod-even.query(pos-1)));odd.modify(pos,f[i]);}else{f[i]mod_add(mod_add(odd.query(m),mod-odd.query(pos-1)),even.query(pos));even.modify(pos,f[i]);}}coutf[n]endl;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容