前缀和01蓝桥OJ3382区间次方和前缀和多次查询预处理取模题目链接区间次方和这道题是一道较为基础的前缀和题目问题在于题目给的nm数量级较大1e5。最直接的想法是用前缀和加速区间求和于是对每个元素a[i]求k次方并依次存入一维数组prefix[i]主要代码如下while(m--){intl,r,k;cinlrk;vectorlonglongprefix(n1,0);for(inti1;in;i){prefix[i](prefix[i-1]pow_mod(a[i],k)%mod;}cout(prefix[r]-prefix[l-1])%modendl;}但是这样写代码有两个非常严重的问题1.首先是时间复杂度的问题每次查询是O(n)m次查询时间复杂度为O(n*m)而nm的数量级最大又为1e5则必然会导致TLE的情况。2.其次是取模运算的问题最后输出的代码为cout (prefix[r]-prefix[l-1])%mod endl; 我们必须注意到prefix[i]在先前的数据计算存入时已经进行过取模运算这就导致可能出现prefix[r]小于prefix[l-1]的情况导致最后WA。解决方案1.时间复杂度问题我们注意到题目中的k的范围较小是15且数组a是固定的所以我们可以预先为每个k分别建立前缀和数组。从而我们可以想到用一个二维数组prefix[k][i]来分别存储前i个元素的k次方和这样我们先进行预处理的时间复杂度是O(5 * n)再进行查询操作的时间复杂度为O(m)这样总复杂度就从O(n * m)优化到了O(nm)即O(n)复杂度。2.取模运算问题最后的输出中我们只要将(prefix[r]-prefix[l-1])%mod写成(prefix[r]-prefix[l-1]mod)%mod即可这样能使得输出结果为正。最后我们按照上述思路再完整地写一遍代码代码如下#includebits/stdc.husingnamespacestd;usinglllonglong;constintN1e55;ll a[6][N],prefix[6][N];constll mod1e97;intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intn,m;cinnm;for(inti1;in;i){cina[1][i];}for(inti2;i5;i){for(intj1;jn;j){a[i][j]a[i-1][j]*a[1][j]%mod;}}for(inti1;i5;i){for(intj1;jn;j){prefix[i][j](prefix[i][j-1]a[i][j])%mod;}}while(m--){intl,r,k;cinlrk;ll res0;res(prefix[k][r]-prefix[k][l-1]mod)%mod;//这里非常重要如果减法不取模可能导致结果为负数因为prefix的计算之前就已经取过一次模了因此prefix[k][r]可能小于prefix[k][l-1]coutresendl;}// 请在此输入您的代码return0;}最后总结一下从这道题当中我们能体会到前缀和的精髓在于一次预处理多次使用不能每次查询都重建且面对多组查询且查询参数范围有限如k小于等于5时可以考虑以空间换时间预计算所有情况。
前缀和01：蓝桥OJ3382区间次方和
发布时间：2026/8/2 7:55:55
前缀和01蓝桥OJ3382区间次方和前缀和多次查询预处理取模题目链接区间次方和这道题是一道较为基础的前缀和题目问题在于题目给的nm数量级较大1e5。最直接的想法是用前缀和加速区间求和于是对每个元素a[i]求k次方并依次存入一维数组prefix[i]主要代码如下while(m--){intl,r,k;cinlrk;vectorlonglongprefix(n1,0);for(inti1;in;i){prefix[i](prefix[i-1]pow_mod(a[i],k)%mod;}cout(prefix[r]-prefix[l-1])%modendl;}但是这样写代码有两个非常严重的问题1.首先是时间复杂度的问题每次查询是O(n)m次查询时间复杂度为O(n*m)而nm的数量级最大又为1e5则必然会导致TLE的情况。2.其次是取模运算的问题最后输出的代码为cout (prefix[r]-prefix[l-1])%mod endl; 我们必须注意到prefix[i]在先前的数据计算存入时已经进行过取模运算这就导致可能出现prefix[r]小于prefix[l-1]的情况导致最后WA。解决方案1.时间复杂度问题我们注意到题目中的k的范围较小是15且数组a是固定的所以我们可以预先为每个k分别建立前缀和数组。从而我们可以想到用一个二维数组prefix[k][i]来分别存储前i个元素的k次方和这样我们先进行预处理的时间复杂度是O(5 * n)再进行查询操作的时间复杂度为O(m)这样总复杂度就从O(n * m)优化到了O(nm)即O(n)复杂度。2.取模运算问题最后的输出中我们只要将(prefix[r]-prefix[l-1])%mod写成(prefix[r]-prefix[l-1]mod)%mod即可这样能使得输出结果为正。最后我们按照上述思路再完整地写一遍代码代码如下#includebits/stdc.husingnamespacestd;usinglllonglong;constintN1e55;ll a[6][N],prefix[6][N];constll mod1e97;intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intn,m;cinnm;for(inti1;in;i){cina[1][i];}for(inti2;i5;i){for(intj1;jn;j){a[i][j]a[i-1][j]*a[1][j]%mod;}}for(inti1;i5;i){for(intj1;jn;j){prefix[i][j](prefix[i][j-1]a[i][j])%mod;}}while(m--){intl,r,k;cinlrk;ll res0;res(prefix[k][r]-prefix[k][l-1]mod)%mod;//这里非常重要如果减法不取模可能导致结果为负数因为prefix的计算之前就已经取过一次模了因此prefix[k][r]可能小于prefix[k][l-1]coutresendl;}// 请在此输入您的代码return0;}最后总结一下从这道题当中我们能体会到前缀和的精髓在于一次预处理多次使用不能每次查询都重建且面对多组查询且查询参数范围有限如k小于等于5时可以考虑以空间换时间预计算所有情况。
)
)
