k 次方和问题浅述

Posted on 2022-11-05 In OI/ICPC

前置技能：线段树，组合数学，矩阵。

次方和问题，实际上是维护的一类问题。再进行深入研究，实际上是一系列推大式子的问题。

下面分组介绍。

幂和问题

幂和问题即为求的一类问题，其中常量为。目前的做法有以下几种。

显然，直接利用枚举与快速幂可以做到这个时间复杂度。

考虑到为一个积性函数，所以我们可以用线性筛的方法解决。对于质数直接利用快速幂求解，对于合数则拆出任意一个因子进行计算。由于只对质数进行快速幂，根据素数定理，我们可以估计这个算法的复杂度为。然后做前缀和即可，复杂度仍为。

实现见这里。

公式是：

推导见这里。

由于 Lagrange 基本多项式的分子分母特殊，因此利用 Lagrange 插值可以做到的复杂度。需注意到幂和为一个次多项式。

具体可参考 riteme 的博客。

求：

输出答案对取模后的值。。

有一个比较常用的转化：

注意第四步的配凑和倒数第二步中组合数的化简，由于它能覆盖到的所有数，因此可化简为。因此总时间复杂度，空间复杂度。

区间次方和问题是维护数列，并查询或有关信息的一类问题。

当时，甚至可以回答询问……

当时，只需要维护区间和即可，根据修改的要求维护线段树。

一般询问的是和的情况。

线段树问题我们一般维护询问，当询问区间和，区间修改为区间加法时，有如下推导：

可以观察到，要维护次方的话一定要维护所有次方和，在更新的时候也需要从高次到低次幂维护。

但是对于更高次数时，这样维护太奔溃了，对于高次情况我们考虑使用矩阵来维护。

对于线段树的每个区间，维护如下矩阵：

对于区间加法，即可对于每个区间右乘（为区间增量）：

考虑到加法可以合并，我们可以直接维护区间加标记，下传时再构建上述矩阵进行标记下传中的维护。对于乘法，和区间乘法一样类似操作即可。因此整个操作的复杂度为。

当较小时，直接维护效果更好，复杂度为，并且常数很小。