似乎莫得人是不用树剖的w

但是为什么的一只$\log$乱搞被树剖的两只$\log$爆踩啊

是因为我实现的太丑了吗

不管了直接讲做法好了

有趣的矩阵乘法

（为方便，下文中“大号宝石”代指连续的$m$个分裂出来的宝石，“小号宝石”代指未分裂的单个宝石）

首先，我们观察这题，考虑$DP​$，设状态$f_i​$表示已经取了$i​$个单元的方案数的不难推出一个朴素的$O(n^2) DP​$方程$f_i = \displaystyle\sum_{i - j \geq m} f_j +1​$（可以理解成上一个大号宝石放的位置，最后一个$1​$即为全部用小号宝石填满的方案）

我们再仔细看看这个式子，加个前缀和，不难优化到$O(n)$，然而数据范围$n \leq 10^{18}$，这让我们考虑$O(\log n)$级别的算法，我们接下来考虑矩阵乘法优化这个式子。

又双叒叕是题外话

今天模拟考是原题大战。

$T1​$是这题。
$T2$是某次$CF\ Div1\ E$题。
$T3​$反正是某道神仙题。

像我这样的菜鸡只能来做做相对可做的T1

虽然只是相对可做但是还是被全场切穿了啊喂

内心OS：这个不订正的理由真的nice

本篇题解讲述的为非完美做法，但是可以骗到96分

说实话我在网上找了好久结果都是这个$O(n^2)$的非正解树型$DP$

听说有个$O(N)​$的正解在某篇论文里？

算了反正我也看不懂

所以我接下来就介绍一下这个$O(n^2)$的树型$DP$吧QwQ

顺手丢一下我学习的这篇blog​吧

简单递归

首先我们如果要消灭一段区间$[l, r]$，我们可以有三种选择：

• 如果$[l, r]​$区间内没人，那么直接花费$A​$的代价将这段摧毁
• 如果$r > l​$（即这段区间长度$>2​$），可以选择把它切割成$\left[ l, \lfloor \frac{l + r}2\rfloor\right]​$ $\left[\lceil \frac{l + r}2\rceil, r\right]​$两段
• 如果$[l, r]$区间内有人，直接花费$b (r - l + 1)x$的代价将其摧毁。

题外话

我本来自己想到的的做法是跟别的大多数题解一样的

但是$LJC00118$大仙跟我讲了他的做法，据说常数更小一些，于是我就过来发（水）题（社）解（区）了（分）。

$Day\ 0$

早上八点的飞机从杭州飞到广东中山纪念。

飞机上跟旁边的$sjn$神犇聊了一会之后开始颓废，后来敲了$fhq\ Treap$、最大流、费用流三个板子。

到了广东之后做了3个小时的公交车

到了中山纪念之后觉得宿舍略破，不过至少有电QwQ

试了个机，T1水题，T2据说是去年PKUSC的D1T2，想出了DP的状态定义不会转移，结果后来Sooke教我了一下，感觉不是特别想敲=-=

试完机之后还有蛮长的一段时间吃饭，于是我们就打了一盘狼人杀（法官真好玩）

饭菜一般般，坐我旁边的Sooke想找人面基，但是最后也就来的路上遇到了bztQwQ

晚上吃完饭，又来了一盘狼人杀（我还是法官）（双预言家真好玩）

现在是晚上7点，我躺在床上跟LJC00118一起写游记

真是充（颓）实（废）的一天

​ 前段时间在机房里几个大爷的墙裂安利下学了发$fhq\ treap$ 于是就顺带着把$fhq\ treap$的区间操作给学了（比$Splay$的好理解多了）

似乎这么一点字太少了？那我放张图=-=

题外话

我们模拟赛考了这题。

模拟赛大概还剩一个半小时的时候，我想出了这题，并且说

“要是我这没A掉，我就不交卷了”

于是我就没有A掉。

其实赛后半个小时左右就调出来了（我才不会告诉你我比赛的时候那个建模是有锅的呢）

Ⅰ 什么是珂朵莉？

珂朵莉是世界上最幸福的女孩，没有之一，不接受任何反驳。