由于今天 div 1 换了题，导致 div 1 和 2 就只有 1 道题一样，就只放 div 2 的题算了，而且还没有改完……有一道是线段树。其实我很不擅长的就是线段树了……多练练。

今天冬月廿八，感觉又感冒了……希望快快好起来。说到这里，想起一件事情。昨天放学的时候在路口看到一辆从路边启动的汽车撞倒了一辆正常行进中的摩托车（兴许是电瓶车），那个场面……并没有那么严重，汽车刚刚启动而已，希望人没事，但是看起来也没啥事，还是希望没事🙏🙏🙏🕯🕯🕯。

题解

今天的题目还是很有难度的。来简单讲一下。

A. 纸条

就是把一个长为的纸带切成很多段，有个地方不能下刀，然后每一段上填数且满足这个数是这一段长度的因数且小于等于。。

显然容易想到的方法，就是前缀和存一下，然后就想到了矩阵快速幂。暴力求是不行的，可以预处理出矩阵。然后每一段直接乘以向量，就不用矩阵乘法了，这是一个很好的优化，可以记住！矩阵的边长压缩一下就是，要存一下当前的值。然后复杂度就是。前面预处理很快，1 ms 左右就能算完。后面算矩阵和向量乘法的时候要注意，按照我的做法如果暴力乘起来取模会 TLE。这个时候使用 __int128，然后最后再取模速度直接快了将近 10 倍！卡常小技巧！

这道题我用了一个宏，但是变量没打括号，最开始挂了！警示后人！

B. 染色问题

题意很简单，个点条边的联通无向图，种染色给每个点，边两端不同色，不一定所有颜色都用。

然后。

显然 NPC。正解是什么呢？就是考虑一条边两端点颜色相同和不相同的这两个权值，一种染色方案就是这些边对应权值乘起来。那么初始都是。然后找到度数为的点删掉，最后乘上就可以。还要再找到度数为的点，删掉这个点然后连上两边。那么显然如果同色就要乘上，否则乘上，然后最后剩下的图一定每个点度数大于，能得到，又因为上面的不等式，显然可以状压转移了。

这里还有另一种更显然的做法。就是先搞出 dfs 树，然后有额外边对吧。然后暴力枚举额外边中任意一个端点的“相对颜色”，然后暴力树上 dp 就可以了。最后假设 dfs 到了这几个特殊点颜色总共种，那么乘以一个就行了。

P.S. 我们最开始没有看懂第二种的代码，我把它扔给文心一言，没有任何题面的提示，就是叫它解读代码，然后它竟然识别出了这个代码是 k 染色问题还大致说了每个变量的作用。太抽象了！难以置信。网上唯一搜到的 csdn 博客还要钱……虽然继续问它它也说不清楚，但能说出是染色问题还是很厉害的！

C. 序列

看起来是个线段树板题啊。

你需要维护两个初值为的序列和；

共次操作，每次操作给出，将修改为，然后对将加上，然后查询。。

看题解很线段树板子啊，但我线段树这个科技树点得不是很多啊。

题解是这样说的。

离线扫描线扫序列，问题转化为维护时间维对应的序列，区间对取，全局标记当前为一个新的版本，查询前缀历史和。可以用线段树维护：

区间信息需要记录区间最小值、区间严格次小值、区间最小值个数、区间和、区间历史和；

标记需要记录对取的（若没有则为）、取前标记了几次版本、取后标记了几次版本、取后每次标记版本时的和；

对结点应用标记时，如果标记的小于等于区间最小值，则标记需要更新为为，取后每次标记版本时的和改为区间最小值乘取后标记了几次版本；

其余部分的处理使用 区间最值问题与历史最值问题 的标准做法。

总时间复杂度。

后记

没啥可记的呢？没意思。希望大家能找到自己的归属。