2023暑假杭电多校做题记录
杭电01
01
原本以为单组询问要O(log)做，想了很久不会。
发现数据范围是3000，于是直接暴力枚举相遇的点，excrt解两个同余方程即可，通过预处理可以做到\(O(nm+mlog)\)
然后确实有加强版的题目CF500G
大概可以转化成区间余数最小的问题，但是没研究明白，sad
杭电02
08
线段树维护矩阵板题，比赛时很纠结效率能否通过，但时间不够甚至没调对（差一个线段树修改的范围判断忘加了，以后不管多熟悉的算法，还是尽量抄模板以完全避开低级错误吧）
至于效率，首先询问的部分是向量乘一些矩阵，可以从左到右依次乘,每次是\(O(11^2)\)，但修改就必须\(O(11^3)\)，这样做就能通过了；然后还有两个基于本题矩阵性质的优化：
1.注意到单个矩阵是上三角的，所以乘积也是上三角的；那么计算乘法时，只要算两个矩阵都不为0的部分（即\(i\le k\le j\)），可以除掉6倍的常数，分析出这个就不用纠结了
2.考虑减小取模次数，矩阵大小仅有11，所以可先用ull的矩阵存不取模的结果，最后进行\(O(11^2)\)次取模
加上这两个优化后就在1s以内了。