题目描述
给定一个长度为 n 的序列 $a_1,a_2,a_3,...,a_n$ 与一个参数 $k$ 。
现有 $q$ 次询问，每次询问一个区间$[L,R]$，请你求出该区间内所有子集和中，有多少个子集和恰好是 $k$ 的倍数，答案对$998244353$取模。（注意：所有子集中包含空集）
算法思路
本题采用优雅的暴力结构——分块。
预处理
将序列分成$M=\sqrt{n}$块，每块分别记录三类数据$lr[M][M][20],rr[M][M][20],br[M][20]$。
$lr[i][j][r]$表示第$i$块，从块内倒数第$1$个数到正数第$j$个数所有组合中余数为$r$的个数，共$M$个块，每块需要$O(Mk)$，合计$O(nk)$。
$rr[i][j][r]$表示第$i$块，从块内正数第$1$个数到正数第$j$个数所有组合中余数为$r$的个数,共$M$个块，每块需要$O(Mk)$，合计$O(nk)$。
$br[i][r]$表示第$i$块，从头至尾所有组合中余数为$r$的个数,可以复用$rr[i][M][r]$。
注意根据乘法原理，例如余数2的个数*余数3的个数就是增加的余数5的个数。 我们可以$O(k^2)$来合并两个区间。
为了加快查询速度，我们再预处理一类数据$ss[M][M][20]$,$ss[i][j][r]$表示从第i块到第j块所有组合中余数为$r$的个数。
在求解 $ss[i][j]$ 时我们可以利用$ss[i][j-1]$ 和$br[j]$ 合并来得到，共有$M^2$块需要合并。
至此，我们预处理完毕，预处理时间复杂度$O(nk + nk^2)$。
查询
查询可以分三类。
- 若$l,r$在同一块内，则直接暴力计算即可，$O(Mk)$。
- 若分散$l,r$分散在两个相邻的块，假设 $l$ 在 $i$ 块,第 $s$ 个位置，$r$ 在 $j$ 块第 $t$ 个位置，直接$O(k)$快速合并$lr[i][s]$与$rr[j][t]$记录的余数个数信息，最终答案只需统计余数为0个数，故$O(k)$。
- $l,r$相距较远。同样假设 $l$ 在 $i$ 块,第 $s$ 个位置， $r$ 在 $j$ 块第 $t$ 个位置。现合并$lr[i][s]$与$rr[j][t]$记录的余数个数信息$O(k^2)$，再将合并结果与$ss[i+1][j-1]$记录的余数个数信息合并$O(k)$。
对于查询来说，第3类查询数量最多，因此单次查询复杂度可认定为$O(k^2)$。
总体时间复杂度
$O(nk^2+qk^2)$即$O((n+q)k^2)$
类似数据结构 猫树
猫树，一种改版线段树。思想和我的这种分块方式类似，所以我管我搞出来的这个分块叫做猫块。
评论 (0)