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

想要成为编程高手？那就来试试全网最全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 枚举智乃酱的前缀和与差分题解