有趣的矩阵乘法

(为方便,下文中“大号宝石”代指连续的$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)$级别的算法,我们接下来考虑矩阵乘法优化这个式子。

简单递归

首先我们如果要消灭一段区间$[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$的代价将其摧毁。
DP

$Day\ 0$

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

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

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

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

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

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

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

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

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

真是充(颓)实(废)的一天