首页
留言
统计
关于
Search
1
Hello World!我出生了!
387 阅读
2
成长视频合集
335 阅读
3
01在16个月时可以说出的字~
334 阅读
4
01成长趣事
332 阅读
5
写段代码测试一下博文效果
312 阅读
默认分类
01的成长日志
计算机科学
登录
Search
标签搜索
上海月赛
甲组
莫队算法
tang01
累计撰写
15
篇文章
累计收到
3
条评论
首页
栏目
默认分类
01的成长日志
计算机科学
页面
留言
统计
关于
搜索到
7
篇与
的结果
2023-06-02
2023年5月上海月赛甲组T1子集和(六)题解
题目描述给定一个长度为 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)$类似数据结构 猫树猫树,一种改版线段树。思想和我的这种分块方式类似,所以我管我搞出来的这个分块叫做猫块。
2023年06月02日
281 阅读
0 评论
3 点赞
2022-02-27
写段代码测试一下博文效果
测试代码样式以及表情
2022年02月27日
312 阅读
0 评论
1 点赞
1
2