首页
留言
统计
关于
Search
1
Hello World!我出生了!
387 阅读
2
成长视频合集
335 阅读
3
01在16个月时可以说出的字~
334 阅读
4
01成长趣事
332 阅读
5
写段代码测试一下博文效果
312 阅读
默认分类
01的成长日志
计算机科学
登录
Search
标签搜索
上海月赛
甲组
莫队算法
tang01
累计撰写
15
篇文章
累计收到
3
条评论
首页
栏目
默认分类
01的成长日志
计算机科学
页面
留言
统计
关于
搜索到
15
篇与
的结果
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-06-15
01在19个月时可以说出的字~
2022/6/15 又来了,玩坏了,修好了,蒙圈拉,咋地,没电了,接住了,捞鱼2022/6/21 开火车, 放鞭炮了,破壞王,搞破壞,完犢子了,能開了,開汽車,消防車 三轮车,快递车,獨輪車,垃圾车,工程车,太難看了,哎呀我去,发光了,双胞胎
2022年06月15日
289 阅读
0 评论
1 点赞
2022-04-27
01在18个月时可以说出的字~
2022/4/27 坑,踹,浣,熊,象,蹲 2022/4/29 淘,气,包,塞,神,转,挂,晃,拆,扣,揪,薅2022/5/2 毛,被,冲,烫,吹,怕,热,下,太,三2022/5/3 妹妹,可爱2022/5/8 爸爸扒扒梅梅(吃草莓)!!!,按,挤,浪,优秀!!2022/5/12 撞,硬,摘2022/5/16 一字字的说:三国杀 南蛮入侵 顺手牵羊 过河拆桥 万箭齐发 大丈夫能屈能伸2022/5/17 厉害2022/5/18 蛋糕,坏蛋,高兴,开心,胳膊,掰碎(正式进入词语时代)2022/5/19 这家伙 2022/5/20 埋汰,稀罕,姥(孬)爷,葡萄,屁股,窗户 ,调皮,冒烟2022/5/21 尖锐,衣服, 认识Σ 西格玛,字母n2022/5/23 汽车,卡车,掰开,飞机,嘟乐2022/5/24 吓懵,锁头,泥巴,下雨,打雷
2022年04月27日
232 阅读
0 评论
0 点赞
2022-03-31
01生长发育数据
2022/3/31 更新 年龄:17个月零5天 身高:85.3cm 体重:11.7kg 脚长:14cm 头围:47cm2022/6/15 更新 年龄:19个月零5天 身高:88.5cm 体重:11.7kg 脚长:15cm 头围:48cm2023/2/12 更新 年龄:28月 身高:95cm 体重:13.7kg 脚长:17cm 头围:50cm2023/8/12 更新 年龄:34月 身高:99.5cm 体重:14.5kg 脚长:?cm 头围:?cm
2022年03月31日
228 阅读
0 评论
0 点赞
2022-03-31
01在17个月时可以说出的字~
2022/3/31 更新 看,爷,吃,七,康,一,光 2022/4/2 更新 该,开,拆,葱,菜,太,臭,鸡 2022/4/7 更新 框,心,星,刺,车,抱,爱,兔(吐),泡,抛,怕 2022/4/10 更新 转,壮,蛋,尬,称,英 2022/4/11 更新 胖,草,够 , 大葱!!!,拆它!!!,扒2022/4/12 更新 扇,下,虾2022/4/13 更新 猫,窗,门,爷爷,请,枪 2022/4/14 更新 线,莓,棋 2022/4/15 更新 烟 2022/4/16 更新 抽,1,2,3,4,5,6,7,8!!!!!!!,酸,胎,搭2022/4/17 更新 风,半,杯,Y歪,孬2022/4/20 更新 风车,懒蛋**2022/4/23 更新** 瓶,灌,黄瓜,转,胎轮,爸爸抱! **2022/4/25 更新** 脱光,耶 ,认识阿拉伯数字2, 笑,快
2022年03月31日
244 阅读
0 评论
2 点赞
1
2
3