打卡信奥刷题（3251）用C++实现信奥题 P8590 『JROI-8』这是新历的朝阳，也是旧历的残阳

P8590 『JROI-8』这是新历的朝阳，也是旧历的残阳

题目背景

少女于海边伫立，凝视着落日最后的余晖
“已然过去了呢，旧历的一年…”

已获得转载授权。

题目描述

给定序列{an}\{a_n\}{an​}，满足每一项都不小于前一项。对于所有不超过kkk的正整数mmm，询问如果将aaa分成mmm段（可以有空段），并给从前往后第iii段内的每个数都加上iii，增加后的∑j=1naj2\sum\limits_{j=1}^n a_j^2j=1∑n​aj2​最大是多少。询问相互独立，即每次询问时给每个数加的值不保留到下一次询问。

例如，对于序列{−3,1,2,2}\{-3,1,2,2\}{−3,1,2,2}，若m=5m=5m=5，则一种分段方式是[−3][][1,2][][2][-3][][1,2][][2][−3][][1,2][][2]，增加后的序列是−2,4,5,7-2,4,5,7−2,4,5,7，此时∑j=1naj2=94\sum\limits_{j=1}^n a_j^2=94j=1∑n​aj2​=94。

记m=im=im=i时的答案（即此时最大的∑j=1naj2\sum\limits_{j=1}^n a_j^2j=1∑n​aj2​）为qiq_iqi​，出于良心考虑，你只需要输出(∑i=1kqi) mod 998244353\left(\sum\limits_{i=1}^k q_i\right) \bmod 998244353(i=1∑k​qi​)mod998244353即可。标准程序不基于特殊的输出方式，即能独立求出每一个qiq_iqi​。

输入格式

第一行两个正整数n,kn,kn,k，同题意。

接下来一行nnn个整数，表示{an}\{a_n\}{an​}。

输出格式

一行一个整数，表示(∑i=1kqi) mod 998244353\left(\sum\limits_{i=1}^k q_i\right) \bmod 998244353(i=1∑k​qi​)mod998244353。

输入输出样例 #1

输入 #1

4 3 -3 1 2 2

输出 #1

141

说明/提示

【样例解释】

当m=1m=1m=1时，最优策略是[−3,1,2,2][-3,1,2,2][−3,1,2,2]，q1=(−2)2+22+32+32=26q_1=(-2)^2+2^2+3^2+3^2=26q1​=(−2)2+22+32+32=26。

当m=2m=2m=2时，最优策略是[−3][1,2,2][-3][1,2,2][−3][1,2,2]，q2=(−2)2+32+42+42=45q_2=(-2)^2+3^2+4^2+4^2=45q2​=(−2)2+32+42+42=45。

当m=3m=3m=3时，最优策略是[−3][][1,2,2][-3][][1,2,2][−3][][1,2,2]，q3=(−2)2+42+52+52=70q_3=(-2)^2+4^2+5^2+5^2=70q3​=(−2)2+42+52+52=70。

则(∑i=1kqi) mod 998244353=(q1+q2+q3) mod 998244353=(26+45+70) mod 998244353=141\left(\sum\limits_{i=1}^k q_i\right) \bmod 998244353=(q_1+q_2+q_3)\bmod 998244353=(26+45+70)\bmod 998244353=141(i=1∑k​qi​)mod998244353=(q1​+q2​+q3​)mod998244353=(26+45+70)mod998244353=141。

【数据范围与约束】

C++实现

#include<bits/stdc++.h>#defineXD114514usingnamespacestd;intn,k;constintmod=998244353;longlonga[1000010],ans;intmain(){cin>>n>>k;for(inti=1;i<=n;i++){scanf("%lld",&a[i]);}for(inti=1;i<=k;i++){for(intj=1;j<=n;j++){if(abs(a[j]+1)>abs(a[j]+i)){//判断放最左面还是最右面ans+=(a[j]+1)*(a[j]+1);ans%=mod;}else{ans+=(a[j]+i)*(a[j]+i);ans%=mod;}}}cout<<ans;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容