P10893 城市化发展委员会题目背景MLE 大帝曾说过所以为了应对这种情况我们设立了城市化发展委员会。题目描述在高中的校园里我们常常能看到随机刷新的小情侣对于他们之间的情感对于 OIer 来说还是太过于高深了即使是退役的 AzureHair 也无法理解这一行为但是作为自命的城市化发展委员会的常委他有自己的一套理解方法。他认为女生往往对男生十分的严格。一天开始时男生在女生的心里的积分会加111而如果当天惹女生生气了xxx次积分就会在此基础上减xxx。积分会不断累计一旦小于等于000就可能导致去城市化的严重后果。现在威廉在和珂朵莉进行一种城市化行为威廉在纳西妲的帮助之下获得了超能力一是他可以预知到接下来一个周期的积分变化情况初始的周期长度为nnn二是他可以选择从任意一天开始开始前的日子将会被拼接到最后一天之后。他从每一天开始都尝试过一次后发现了aaa个能使得他不被去城市化的起始日期。随后他会将这若干种情况下的序列按照起始日期的先后拼在一起变成一个长度为原先aaa倍的周期。他如此重复操作kkk次由于一天天地试太累了威廉只想知道最后一次操作后有多少个起始日期能让自己不被去城市化对998244353998244353998244353取模。形式化地说我们称满足前缀和始终大于000的数列为 “安全的”。对于一个长为nnn的数列AiA_iAi​根据以下算法构造出数列Ai1A_{i1}Ai1​初始时Ai1A_{i1}Ai1​为空。重复执行nnn次若AiA_iAi​是安全的将其整个接到Ai1A_{i1}Ai1​末尾。将AiA_iAi​循环左移一位即令Aij←Aij1 mod nA_{i_j} ← A_{i_{j1 \bmod n}}Aij​​←Aij1modn​​。现在给定A0A_0A0​满足其各项均不大于 1。从A0A_0A0​开始按上述规则生成数列A1A_1A1​到Ak1A_{k1}Ak1​请求出Ak1A_{k1}Ak1​与AkA_kAk​的长度比这个值只要存在就一定是整数请输出它对998244353998244353998244353取模的值。特别地如果AkA_kAk​为空请输出0。输入格式普通题意共两行第一行两个整数nnn和kkk表示初始的周期长度和操作次数。第二行nnn个小于等于 1 的整数表示每天的积分变化。形式化题意共两行第一行两个整数为A0A_0A0​的长度nnn以及kkk。第二行是A0A_0A0​。输出格式一行一个整数表示答案对998244353998244353998244353取模的结果。输入输出样例 #1输入 #18 0 1 1 -2 1 1 -1 0 1输出 #12输入输出样例 #2输入 #26 0 1 1 -4 -5 1 -4输出 #20说明/提示【样例解释1】对于样例 #1 的数据初始周期为1 1 -2 1 1 -1 0 1。从每一天开始得到的序列分别是1 1 -2 1 1 -1 0 1 1 -2 1 1 -1 0 1 1 -2 1 1 -1 0 1 1 1 1 1 -1 0 1 1 1 -2 1 -1 0 1 1 1 -2 1 -1 0 1 1 1 -2 1 1 0 1 1 1 -2 1 1 -1 1 1 1 -2 1 1 -1 0只有从第 4 天和第 8 天开始的序列是满足条件的。形式化题意A1{1,1,−1,0,1,1,1,−2,1,1,1,−2,1,1,−1,0}A_1\{1,1,-1,0,1,1,1,-2,1,1,1,-2,1,1,-1,0\}A1​{1,1,−1,0,1,1,1,−2,1,1,1,−2,1,1,−1,0}长度为 16因此应输出 2。【样例解释2】可以证明不存在合法的方案。喂样例全都k0k0k0是不是太过分了数据范围对于15%15\%15%的数据保证1≤n≤101\le n \le 101≤n≤101≤k≤51\le k \le 51≤k≤5。对于另外25%25\%25%的数据保证k0k0k0。对于100%100\%100%的数据保证1≤n≤1061\le n\le 10^61≤n≤1060≤k≤1060 \le k \le 10^60≤k≤106−109≤A0i≤1-10^9 \le {A_0}_i \le 1−109≤A0​i​≤1。C实现#includebits/stdc.h#definemod998244353usingnamespacestd;intn,k;inta[2000005];longlongs[2000005];longlongans1;structnode{intl,r,siz;intminn;}t[4000005];voidbuild(intx,intl,intr){t[x].ll;t[x].rr;t[x].sizr-l1;if(lr){t[x].minns[l];return;}intmid(lr)/2;build(x1,l,mid);build(x1|1,mid1,r);t[x].minnmin(t[x1].minn,t[x1|1].minn);}longlongquery(intx,intll,intrr){if(t[x].lrr||t[x].rll)return0x3f3f3f3f;if(t[x].lllt[x].rrr)returnt[x].minn;returnmin(query(x1,ll,rr),query(x1|1,ll,rr));}boolflag1;intmain(){scanf(%d%d,n,k);for(inti1;in;i){scanf(%d,a[i]);a[in]a[i];s[i]s[i-1]a[i];if(s[i]0)ans0;}if(s[n]0){cout0;return0;}build(1,1,n);for(inti1;in;i){if(query(1,i1,n)-s[i]0query(1,1,i)s[n]-s[i]0)ans;}for(inti1;ik;i){ans(ans*ans)%mod;}printf(%lld,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容