HBC225629Touring cities,枚举智乃酱的前缀和与差分题解 (前缀和、差分)

三寸光阴七寸执念 基本结构 146 0
想要成为编程高手?那就来试试全网最全C++题库,让您在练习中快速成长。
智乃酱最近学习了前缀和、差分,她现在对于这两个操作产生了浓厚的兴趣, 具体来说,前缀和是这样一种操作,假设s{s}s数组是a{a}a数组的前缀和数组,则有 {s0=a0si=ai+si1(i≥1)left{begin{matrix}s_0=a_0; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; \ s_i=a_{i}+s_{i-1}(i geq 1)end{m

智乃酱最近学习了前缀和、差分。她现在对于这两个操作产生了浓厚的兴趣。 具体来说,前缀和是这样一种操作,假设s{s}s数组是a{a}a数组的前缀和数组,则有 {s0=a0                                        si=ai+si−1(i≥1)left{begin{matrix}s_0=a_0; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; \ s_i=a_{i}+s_{i-1}(i geq 1)end{matrix}right.{s0​=a0​si​=ai​+si−1​(i≥1)​ 而差分的操作则是前缀和反过来,假设d{d}d数组是a{a}a数组的差分数组,则有 {d0=a0                                         di=ai−ai−1(i≥1)left{begin{matrix}d_0=a_0; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; , \ d_i=a_{i}-a_{i-1}(i geq 1)end{matrix}right.{d0​=a0​di​=ai​−ai−1​(i≥1)​ 我们将先求出s{s}s数组,再把s{s}s中的值赋值回a{a}a称为对a{a}a数组做一次前缀和,同理,将先求出d{d}d数组,再把d{d}d中的值赋值回a{a}a数组称之为一次差分。 现在我们给定一个长度大小为N{N}N的数组a{a}a和一个参数k{k}k 当k>0{k>0}k>0时,请输出对a{a}a做k{k}k次前缀和后的结果。 当k=0{k=0}k=0时,请直接输出a{a}a数组。 当k<0{k<0}k<0时,请输出对a{a}a做k{k}k次差分后的结果。 为了避免数字过大,你只用输出一个模998244353{998244353}998244353后的模系数字。 也就是说输出的数字应该大小在[0,998244353){[0,{998244353})}[0,998244353)之间,即不要输出负数,如果由于差分导致数字的值小于0,则输出时需要再加上998244353{998244353}998244353变成一个非负整数。

全网最全C++题库,助您挑战自我,突破极限,成为编程领域的佼佼者!

标签: HBC225629Touring cities 枚举智乃酱的前缀和与差分题解