最近看到学长txc爷的blog里写了个“最近写的题目”

然后心血来潮准备自己也弄个这个东西

瞎搞DP

CF出了H没出G 菜的真实

发现$k$从$\texttt{E}$题的$100$变成了$O(10^{12})$，考虑与$k$复杂度无关的做法。

我们考虑$f_{i, j}$表示以$s_i$开始，本质不同的长度为$j$的子序列数量。

线段树乱搞

考虑如果要重排一段区间使得它是回文的是可行的

首先对这段区间的长度分类讨论

哈希 + 二分 + DP

首先看到题面，很容易想到一个$DP$，令$f[i]$为划分到$i$为止的方案数。

然后朴素的暴力转移是$O(n^2)$的，非常显然一个状态$i$能够转移到的$j$是一段连续的，进而想到使用前缀和优化。

$set$瞎搞

首先非常显然，一个矩形$(x1, y1, x2, y2)$的代价就是$\displaystyle\sum_{i = x1}^{x2}\sum_{j = y1}^{y2} h[i][j] - \min_{x1 \le i \le x2, y1 \le j \le y2} h[i][j]$，我们用$f[i][j]$表示以$(i, j)$为左上角的矩形的代价。即矩形$(i, j, i + a - 1, j + b - 1)$的代价。

我们首先考虑如何求出$f[i][j]$。

Round 1

咕咕咕。

回头再补。

set​瞎搞

预处理

我们考虑一下，一只青蛙能够影响的区间是什么

我们发现，如果将每只青蛙能够吃到的文字区间$[l, r]$按照左端点$l$排序，然后把后面的区间和前面的区间的重复部分去掉，那么就可以得到一个青蛙真正可以吃到的蚊子的范围区间

有趣的交互题

我们考虑一件事情

如果我们询问的矩形中有一个端点

那么答案 $\mod 2 = 1$

否则答案 $\mod 2 = 0$

换句话说，就是如果询问到的答案$\mod 2 = 0$，那么这个矩形内要么没有端点，要么有两个端点

似乎莫得人是不用树剖的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)$级别的算法，我们接下来考虑矩阵乘法优化这个式子。