本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-13 23:24:27

:::::info[题目基本信息] 考察：动态规划 DP，轮廓线 DP，状压 DP（$3417$）。
题目简介：
给定一个每条边由 $n$ 个点构成的正三角形，$(i,j)$ 表示三角形中从上往下第 $i$ 行，从左往右第 $j$ 个点，现在有 $m$ 条折线，每条折线从 $(1,1)$ 出发，每次向左下或右下移动，问满足以下条件的折线序列个数（对 $10^9+7$ 取模）：

• $\forall 1\le i<j\le m,1\le p\le n$，第 $i$ 条折线在第 $p$ 行经过的点不位于第 $j$ 条折线经过的点的右边。
• 给定 $k$ 以及序列 $\{a_k\},\{b_k\},\{c_k\}$，对于第 $a_i$ 条折线，在第 $b_i$ 次移动时必须选择左下（$c_i=0$ 时）或右下（$c_i=1$ 时）方的点。

数据范围：

• $1\le n,m\le \color{red}{20}$
• $0\le k\le (n-1)m$
• $\forall i\in[1,k],1\le a_i\le m,1\le b_i<n,c_i\in\{0,1\}$
• $\forall 1\le i<j\le k,(a_i,b_i)\ne(a_j,b_j)$

时间限制：4s。
空间限制：256MB。
::::: 如果我们直接暴力状压 DP，设 $f_{i,S}$ 为考虑到第 $i$ 条折线，同时第 $i$ 条折线的向右移动的时刻构成的集合为 $S$ 时的方案数，那么时间复杂度高达 $\Theta(4^nnm)$，看上去没救了。
我们转化一下问题，转化为在一个 $m\times (n-1)$ 的网格中填数，限定若干个位置必须填 $0$ 或 $1$，同时 $\forall 1\le i<j\le m,1\le k<n$，第 $i$ 行不满 $k$ 个 $1$ 或者第 $j$ 行满 $k$ 个 $1$ 且第 $i$ 行的第 $k$ 个 $1$ 的下标小于等于第 $j$ 行，容易发现这两个问题等价。
在网格图上做状压 DP，我们很容易（也可能不太容易）想到轮廓线 DP，在转化后问题中我们可以设 $f_{i,j,S,p}$ 为考虑到第 $i$ 行第 $j$ 个数下轮廓中填 $1$ 的列编号构成的集合为 $S$，同时第 $i-1$ 行前 $j$ 个数中有 $p$ 个 $1$ 的方案数，容易发现转移为 $\Theta(1)$，这样总复杂度就为 $\Theta(2^nn^2m)$ 的，仍然过不去。
这时我们考虑删去 $p$ 这一维，并把他记录到 $S$ 这一维中，显然在上一行填 $0$ 这一行填 $1$ 时上一行右边离它最近的 $1$ 处可以填 $0$，若填 $0$ 就是填补了这两行间的差距，填 $1$ 就仍然是这一种情况，下一个 $1$ 处可以填 $0$，容易发现正确性成立。
这时状态减少到了 $\Theta(2^nnm)$ 级别，转移仍为 $\Theta(1)$，至于空间问题滚动数组压掉 $i,j$ 两维即可。
时间复杂度为 $\Theta(2^nnm+k)$，空间复杂度为 $\Theta(2^n+nm)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-15 10:29:24

:::::info[题目基本信息] 考察：WQS 二分，生成树（提高+/省选-）。
题目简介：
给定一个有 $n$ 个点 $m$ 条边的无向带权图，每条边要么是白色要么是黑色，求需要有 $k$ 条白边前提下的最小生成树总边权，保证有解。
数据范围：

• $1\le n\le 5\times 10^4$
• $1\le m\le 10^5$
• $0\le k<n$
• 对于图上所有边，边权不超过 $100$。

时间限制：2s。
空间限制：500MB。
::::: 先介绍下 WQS 二分。
:::::success[WQS 二分详解] 设有一凸函数为 $f(x)$，它表示一问题在某一条件为 $x$ 时价值或代价为 $f(x)$，现在我们要求 $f(k)$。
这类问题一般满足：函数 $f(x)$ 在 $D$（$D$ 为定义域）上的最小值好求，同时也好知道该最小值在何处，但 $f(x)$ 在 $x$ 固定时的值不好求，这时我们考虑把 $f(x)$ 转化为整个函数的最小值。
我们钦定 $f(x)$ 为下凸函数，上凸函数同理。画出随便一个 $f(x)$ 的图像：
现在我们要求 $C$ 点通过线性变换转化为整个函数的最小值，由于这是一个凸函数，我们想到用一条直线去切这个函数，就像这样：
这样从函数上的点到直线上的铅垂线的长度变为了变换后函数的值，容易发现此时 $C$ 点成为了函数最小值，这样就可以计算 $C$ 点值了。
实际问题中我们可以二分直线斜率使得快速找到这条切线的斜率，从而得到答案。
::::: 在这道题中，注意到不限制条件时的最小生成树容易得出，所以我们考虑套用 WQS 二分。设 $f(p)$ 为有 $p$ 条白边时的最小生成树总边权，现在我们只需要证明 $f(p)$ 是凸函数，首先我们感性理解下觉得更有可能是下凸函数，因为最小生成树一般不会全是白边或全是黑边。
下面套用下 oi-wiki 的证明：
:::::success[证明] 首先转化一下原问题，由于该函数的定义域为 $[0,n-1]\cap\mathbb Z$，所以证明该函数为下凸函数等价于证明 $\forall i\in(0,n-1)\cap\mathbb Z,f(i)\le\dfrac{f(i-1)+f(i+1)}{2}$。
不妨钦定图上所有边权均不同，对于有相同的情况，选一个趋近于 $0$ 的正实数 $eps$，令这些边加上或减去若干个 $eps$ 就转化为了边权均不同的情况，通过极限可以证明边权有相同的情况。
小结论：设同一个图上存在两棵不同的生成树 $S$ 和 $T$，那么有 $\forall e\in S,\exist f\in T$，使得 $S$ 和 $T$ 交换 $e$ 和 $f$ 后的两个图 $S'$ 和 $T'$ 仍是生成树。
::::success[证明] 设 $e=(u,v)$，$S$ 删除 $e$ 后 $u$ 和 $v$ 断开，由于 $T$ 加上 $e$ 后存在一个环，所以在 $T$ 中可以找到一条在 $u$ 到 $v$ 路径上的一条边，选取任意一条为 $f$，那么容易证明 $T'$ 是一棵生成树。
对于 $S'$ 考虑反证法，删除 $e$ 后的 $S$ 变成了有两个联通分量的森林，如果没有一个 $T$ 图中在 $u$ 到 $v$ 路径上的 $f$ 使得 $S'$ 是生成树，那么所有的 $f$ 的相连的两个点在 $S$ 中都在一个联通分量里，但是由于 $u$ 和 $v$ 在 $S$ 中在两个连通分量里，那么所有的 $f$ 在 $T$ 中也无法连接 $u$ 和 $v$，与假设矛盾，故 $S'$ 是一棵生成树。
证毕。
:::: 设 $S$ 是一棵有 $i+1$ 个白边的最小生成树，$T$ 是一棵有 $i-1$ 个白边的最小生成树，选择一条在 $S$ 中但不在 $T$ 中的白边 $e$，总有一条在 $f$ 中的白边 $f$ 满足交换这两边后 $S'$ 和 $T'$ 还是生成树，对于 $f$ 分类讨论：

• 当 $f$ 是一条既在 $S$ 中又在 $T$ 中的边，那么由于 $e$ 不在 $T$ 中，所以 $e\ne f$，所以 $S'$ 中会出现两条 $f$，故该情况不存在，$f$ 不存在于 $S$ 中。
• 当 $f$ 是一条白边时，则 $S'$ 仍是有 $i+1$ 个白边的生成树，$T'$ 仍是有 $i-1$ 个白边的生成树，由于它们的总边权和仍是 $f(i-1)+f(i+1)$，所以他们均是最小生成树，可以得到两边边权相同，与大前提矛盾，故该情况不存在，$f$ 是黑边。
• 当 $f$ 是存在于 $T$ 中但不存在于 $S$ 中的一条黑边时，$S'$ 和 $T'$ 都是有 $i$ 条白边的生成树，由于它们的总边权和仍是 $f(i-1)+f(i+1)$，容易得到 $f(i)\le\dfrac{f(i-1)+f(i+1)}{2}$。

证毕。
::::: 为了实现减去直线的操作，我们可以给每条白边的边权减去二分的直线斜率，直接对于每条直线斜率跑一遍 Kruskal 即可，当跑出来的最小生成树白边数量最大值不小于 $k$ 时减小直线斜率，否则增大直线斜率。
一个小优化是容易发现白边和黑边分别保持有序，所以在开始我们将两种边分别排序，跑 Kruskal 时跑一轮归并就可以了。
时间复杂度为 $\Theta(m\log m+(n+m)\lpha(n)\log V)$，其中 $V$ 是边权值域，空间复杂度为 $\Theta(n+m)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-16 16:26:49

:::::info[题目基本信息] 考察：倍增，广度优先搜索 BFS，图论（$2700$）。
题目简介：
给定一个有 $n$ 个点 $m$ 条边的有向图，$q$ 次询问，每次询问所有从 $s$ 到 $t$ 的路径中经过的顶点序列字典序最小的路径顶点序列的第 $k$ 项是什么，若不存在路径或不存在最小给出 -1。
数据范围：

• $2\le n\le 3000$
• $0\le m\le 3000$
• $1\le q\le 4\times 10^5$
• $1\le s,t\le n$
• $s\ne t$
• $1\le k\le 3000$

时间限制：2s。
空间限制：250MB。
::::: 注意到 $q$ 较大，$n$ 和 $m$ 较小，考虑预处理。
首先考虑枚举 $s$ 和 $t$ 之间的一个，我们注意到枚举 $t$ 时每个点的下一个要走的点都可以唯一确定，建反图跑一遍就可以，所以我们考虑枚举 $t$。
枚举 $t$，对于每一个点 $i$，找到最小与它相连的的 $j$ 使得 $j$ 能够到达 $t$（这个可以在最开始跑 $n$ 遍 BFS 实现，后文称 $j$ 为 $i$ 的后继），建反图跑一遍判断每个点能否走字典序最小的路径到达 $t$，这样我们就可以判掉 -1，考虑如何处理答案。
枚举 $t$ 的过程中，我们找到了每一个点的后继，我们采用倍增的方式容易预处理并计算出答案。
然后做完了。
时间复杂度为 $\Theta(nm+n^2\log V+m\log m+q\log V)$，空间复杂度为 $\Theta(n^2\log V+m)$，其中 $V$ 为 $k$ 的值域。
:::::warning[坑点] 本做法比较卡空间，倍增数组需要开 short。
:::::

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-17 20:35:58

:::::info[闲话] 我咋从来没写过 Boruvka 的题，菜完了。
::::: :::::info[题目基本信息] 考察：最小生成树，并查集（$2700$）。
题目简介：
一个数轴上有 $n$ 个点，位置编号构成序列 $\{a_n\}$，现在你可以从 $i$ 点跳跃到 $j$ 点，跳跃条件为：

• 有常数 $d,k$，要求 $|a_i-a_j|\in[d-k,d+k]$。

给定 $s,d$，$q$ 次询问，每次给出 $t,k$，问 $s$ 能否通过若干次跳跃移动到 $t$ 上。
数据范围：

• $1\le n,q\le 2\times 10^5$
• $1\le s,t\le n$
• $1\le d,k\le 10^6$
• $\forall i\in[1,n],1\le a_i\le 10^6$ ::::: 容易发现 $k$ 是满足单调性的，更具体地，若 $k$ 满足条件则 $k+1$ 一定满足条件，若 $k$ 不满足条件则 $k-1$ 一定满足条件。所以我们想到预处理每个 $t$ 的分界点。
  要求 $k$ 最小，也就是 $\forall i,j$ 在路径中，要求 $||a_i-a_j|-d|$ 最小，不妨以 $||a_i-a_j|-d|$ 为边权给 $i,j$ 连边，这样就形成了一个图，最后答案就是该图的最小生成树上的路径的边权最大值。
  边权有特殊性质的完全图最小生成树，我们考虑使用 Boruvka。
  :::::success[Boruvka 讲解] 具体地，我们称以下过程为 $1$ 轮：

1. 给每个点找到和它距离最近的点。
2. 将每个点与离它距离最近的点缩成一个点。

进行若干轮这样的操作直到只剩一个点。
::::success[正确性] 容易发现第 1 步类似 Kruskal，第 2 步类似 Prim，Boruvka 的正确性可以通过前两者的正确性（不知道是不是严谨地）推出。
:::: ::::success[复杂度] 容易发现 $1$ 轮最坏情况下是这些点两两配对，点数减少一半，所以设 $T$ 为给每个点找到和它距离最近的点的时间复杂度，那么总时间复杂度就为 $\Theta(n\log n\cdot T)$。
:::: ::::: 本题中套用 Boruvka，容易发现可以使用双指针的方式找到与 $a_i+d$ 和 $a_i-d$ 最接近的点，所以本题均摊下 $T=\Theta(1)$。
然后做完了。
时间复杂度为 $\Theta(n\log n+q)$，空间复杂度为 $\Theta(n)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-18 16:23:04

:::::info[题目基本信息] 考察：Ad-hoc（省选/NOI-）。
题目简介：
给定 $n$ 个序列，第 $i$ 个序列为 $\{a_{len_i}\}$，现在在这 $n$ 个序列各选 $1$ 个数，问所选数字和前 $k$ 小选法的所选数字总和是多少。
数据范围：

• $1\le n,k\le 10^5$
• $\forall i\in[1,n],1\le len_i\le 10$
• $\forall i\in[1,n],j\in[1,len_i],1\le a_{i,j}\le 10^8$

时间限制：1s 至 3s。
空间限制：250MB。
::::: 首先我们可以想到通过一个 $n$ 元组记录一个状态，使用堆可以做到 $\Theta(nk\log nk)$，显然过不了。我们考虑优化。
我们考虑一行一行扩展，这时容易发现若设目前处理的行为 $x$，则前 $x-1$ 行的具体情况并不重要，$x+1$ 行及以后都是 $1$，所以容易设三元组 $(x,y,w)$ 表示处理到第 $x$ 行，同时第 $x$ 行扩展到了第 $y$ 列，同时当前数字和为 $w$，容易扩展：

• 扩展到下一列（前提为 $y\ne len_x$），同时令 $y\leftarrow y+1,w\leftarrow w-a_{x,y}+a_{x,y+1}$。
• 跳到下一行（前提为 $x\ne n$），令 $x\leftarrow x+1$。

但是这样还是不行，每次扩展会直接跳到最后一行，相当于多了 $\Theta(nk)$ 个状态，时间复杂度是 $\Theta(nk\log k)$ 的。
所以我们考虑把跳行这一步省略掉，只在扩展后跳行，这样我们扩展时也能一步扩展，画出来就是这样的一棵递归树（为了清晰，我们以 $\{len_n\}=\{3,2,3\}$ 为例，同时下图的三位数表示最开始的 $n$ 元组）：
这是一棵多叉树，叉数最多能达到 $\Theta(nV)$（其中 $V$ 是 $\{len_n\}$ 的值域）级别，如果我们直接这样做能做到 $\Theta(nkV\log nV)$，还是很慢（怎么更慢了），继续优化。
现在我们唯一的需求就是减少叉数，我们想到可以左儿子右兄弟表示法，更改一下是这样的：

这时就有了一些状态转移方式，为了方便统一，我们把类似 $311\rightarrow 121$ 的边变成 $211\rightarrow 121$，然后再次将状态转化为 $(x,y,w)$，容易发现有 $3$ 种边：

1. $211\rightarrow 311$ 等：即 $(1,2,w)\rightarrow(1,3,w)$，扩展一次（前提条件为 $y\ne len_x$），即同时令 $y\leftarrow y+1,w\leftarrow w-a_{x,y}+a_{x,y+1}$。
2. $211\rightarrow 221$ 等：即 $(1,2,w)\rightarrow(2,2,w)$，跑到下一行扩展一次（前提条件为 $x\ne n$ 且 $y\ne 1$，通过观察递归树容易发现这一行必须扩展了），即同时令 $x\leftarrow x+1,y\leftarrow 2,w\leftarrow w-a_{x+1,1}+a_{x+1,2}$。
3. $211\rightarrow 121$ 等：即 $(1,2,w)\rightarrow(2,2,w)$，撤销一次并跑到下一行扩展一次（前提条件为 $x\ne n$ 且 $y=2$），即同时令 $x\leftarrow x+1,y\leftarrow 2,w\leftarrow w-a_{x,2}+a_{x,1}+a_{x+1,2}-a_{x+1,1}$。

然后我们就做完了这道题，但是还有若干细节。
:::::warning[细节]

1. 为了保证优先队列求第 $k$ 小的正确性，我们要保证后面出现的值不小于前面出现的值，具体地：
   • 对于每个数列，将其从小到大排序。
   • 对于这 $n$ 个数列，将它们按照 $a_{i,2}-a_{i,1}$ 从小到大排序。
2. 上面的扩展方式只适用于 $len_i\ne 1$，对于 $len_i=1$，我们要手动计算答案并把它剔除。
   ::::: 时间复杂度为 $\Theta(k\log k+nV)$，空间复杂度为 $\Theta(nV)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-19 20:34:35

:::::info[闲话] 你说得对，这道题线段树能做，但是我还是花了一天时间复习了点分治并学习了点分树。
::::: :::::info[题目基本信息] 考察：点分树（省选/NOI-）。
题目简介：
给定一棵有 $n$ 个点的树，每个点初始时都是白色，现在有 $q$ 次操作，操作类型有 $2$ 种：

1. 修改一个点的颜色为白色或黑色。
2. 求树上白点两两间最远的距离。

数据范围：

• $1\le n\le 10^5$
• $1\le q\le 5\times 10^5$

时间限制：4s 到 5s。
空间限制：250MB。
::::: 点分树经典题，对点分树进行详解。
:::::success[点分树详解] 众所周知，许多树上暴力过不了的原因是树的高度可能较高从而得到错误的时间复杂度，而点分树就很好的解决了这一点。
点分树是这样建立的：

1. 找到这棵树的重心。
2. 以这棵树的重心为根，将这棵树划分为若干以重心的儿子为根的子树。
3. 将这棵树的重心与子树的重心连边。
4. 递归所有子树。

由于重心的性质，每个子树的大小至少减半，所以最多有 $\log_2 n$ 层，这时有一些暴力就变得可行。
但是由于点分树和原树的形态大相径庭，所以适用范围较小。
::::: 在这个题中，我们先建出点分树，然后维护三个数据结构：

• $a_u$ 表示所有 $u$ 子树内的点到 $u$ 的距离。
• $b_u$ 表示 $u$ 的所有孩子 $v$ 的子树中到 $u$ 的最大距离。
• $ans$ 表示所有点 $u$ 过点 $u$ 的路径长度最大值。

这些在点分树维护的同时就能维护出来，对于修改操作直接从该点往上暴力跳维护即可。
虽然确实细节比较多。
:::::warning[坑点] 用 multiset 维护 $a_u,b_u,ans$ 会被卡常，需要使用可删堆。
::::: 时间复杂度为 $\Theta((n+q)\log^2n)$，空间复杂度为 $\Theta(n\log n)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-21 11:55:49

:::::info[题目基本信息] 考察：树形 DP，动态规划 DP（省选/NOI-）。
题目简介：
$t$ 组数据，每组数据给你一棵有 $n$ 个点的有根树，根为 $1$，你可以进行若干次操作，每次操作为：

• 选择一个叶子结点 $x$，删除一条 $x$ 到 $1$ 的路径上的一条边，并增加一条 $x$ 到 $1$ 的边。

求进行若干次操作后树的直径的最大值。
数据范围：

• $1\le t\le 10^4$
• $1\le n\le 2\times 10^5$
• $\sum n\le 3\times 10^6$

时间限制：2s。
空间限制：512MB。
::::: 容易发现几个性质：

1. 最后的树的所有直径一定过 $1$。 :::::success[证明] 如果存在一条直径不过 $1$，那么将这棵子树的根节点和它的父亲断掉并连接 $1$ 和直径的一个端点（即一次操作）会使直径变长。
   :::::
2. 若在直径最长的基础上让操作数最小，那么最后的直径一定过所有新增的边。 :::::success[证明] 容易发现，如果最后直径不过这条边，那么这次操作就浪费了。
   :::::
3. 在 2 的条件下，操作数上界为 $2$。 :::::success[证明] 结合 1 和 2 容易得到。
   :::::

既然操作数上界为 $2$，那么我们分类讨论：

1. 操作数为 $0$，答案为原树直径。
2. 操作数为 $1$，答案为某个子树的直径拼上一条其它子树的叶子到根根的链。
3. 操作数为 $2$；两条不交的链拼起来。

容易发现操作树为 $0$ 和 $1$ 的情况都是 $2$ 的特例，那么我们进行 $2$ 次操作一定不劣。
现在问题转化为如何求树上两条不交的链的长度和最大值。
不妨枚举子树，分别求出子树内的直径和子树外的直径，拼起来就是答案。
子树内的直径求法是平凡的，问题在于如何求出子树外的直径。
对于两条直径不在 $1$ 的同一儿子的情况，我们直接枚举子树，简单转移即可。
对于位于同一儿子子树内的情况，考虑树形 DP，设 $dp_u$ 为 $u$ 所处的 $1$ 儿子子树内 $u$ 子树以外的最长直径，当从 $u$ 转移到儿子 $v$ 时，需要转移父亲和所有兄弟的贡献。

1. 父亲：令 $dp_v\leftarrow\max(dp_v,dp_u)$。
2. 兄弟之内：令 $\displaystyle dp_v\leftarrow\max(dp_v,\max_{w\in\text{son}_u,v\ne w}f_w)$，其中 $f_w$ 表示 $w$ 子树内的直径，这个东西可以预处理前后缀最值实现。
3. 兄弟之间：记录所有 $u$ 的所有不同儿子的前三长链，之后容易计算。

这样累计答案就做完了。
:::::warning[坑点] 别忘了 $n=2$ 的 corner case。
::::: 时空复杂度均为 $\Theta(n)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-22 09:12:14

:::::info[题目基本信息] 考察：矩阵加速，构造（$3344$）。
题目简介：
给定一个 $n\times m$ 的黑白网格 $a$，定义 $k$ 级分形如下：

• 当 $k=0$ 时，$k$ 级分形是一个黑色网格。
• 否则，对于 $k-1$ 级分形的每一个网格：
  • 如果该格为黑色网格，那么整体替换为所给网格。
  • 否则，整体替换为 $n\times m$ 的白色网格。

问最后的 $k$ 级分形有几个黑色网格四联通分量（对 $10^9+7$ 取模）。
数据范围：

• $1\le n,m\le 1000$
• $0\le k\le 10^{18}$
• 保证当 $k=1$ 时，答案是 $1$。 ::::: 注意到有一个 $k\le 10^{18}$ 的限制，说明要么是结论要么是矩阵加速，我们开始找性质。

1. 当 $k=0$ 时，答案为 $1$。
2. 当两个所给网格上下拼接或左右拼接均有连通块发生拼接，则无论 $k$ 为几，答案均是 $1$。
   容易发现上面“两个所给网格上下拼接或左右拼接均有连通块发生拼接”的充要条件是 $\exist i\in[1,n],a_{i,1}$ 和 $a_{i,m}$ 均为黑色且 $\exist j\in[1,m],a_{1,j}$ 和 $a_{n,j}$ 均为黑色。
3. 当两个所给网格上下拼接或左右拼接均无连通块发生拼接，则无论 $k$ 为几，答案均是 $sum^{k-1}$，其中，$sum$ 表示所给网格中黑色网格的个数。
   该性质充要条件根据 2 同理可得。

上面是比较显然的性质，现在还剩两个所给网格上下拼接或左右拼接其中有一种拼接使得有连通块发生拼接的情况，容易发现左右拼接和上下拼接类似，以上下拼接为例。
:::::success[小技巧] 在代码实现时可以使用矩阵交换行的方式统一成上下拼接。
::::: 由于左右不发生拼接，所以我们可以一行一行考虑。
设 $ans_k$ 为 $k$ 级分形的黑色网格四联通块数量。
正推不好做，考虑容斥，先算出 $sum\cdot ans_{k-1}$ 再减去算重的，就是上下拼接减少的联通块数量，容易发现每个拼接处本质相同，就等于所给网格的上下相邻黑格对数乘上 $k-1$ 级分形的上下拼接减少的联通块个数，前面这项设为 $num$，后面这项设为 $s_{k-1}$，可以直接和 $ans$ 一起算。
最终得到转移方程式：
$$ans_k=sumans_{k-1}-nums_{k-1}$$ $$s_k=numuds_{k-1}$$ 其中，$numud$ 表示所给网格上下拼接时新相拼接的黑格对数。
然后开一个 $siz=2$ 的矩阵加速一下即可。
时间复杂度为 $\Theta(siz^3\log k+nm)$，空间复杂度为 $\Theta(nm+siz^3)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-23 13:56:19

:::::info[题目基本信息] 考察：颜色段均摊（珂朵莉树 ODT）（$2600$）。
题目简介：
给定序列 $\{a_n\}$，你需要进行 $q$ 次共四种操作：

1. 给定 $l,r,x$，进行操作 $\forall i\in[l,r],a_i\leftarrow a_i+x$。
2. 给定 $l,r,x$，进行操作 $\forall i\in[l,r],a_i\leftarrow x$。
3. 给定 $l,r,x$，求 $x\text{thmin}_{i=l}^r(a_i)$。
4. 给定 $l,r,x,y$，求 $\displaystyle(\sum_{i=l}^ra_i^x)\bmod y$。

数据范围：

• $1\le n,q\le 10^5$。
• $\forall i\in[1,n],1\le a_i\le 10^9$。
• 对于所有操作，$1\le l\le r\le n$。
• 对于 3 操作，$1\le x\le r-l+1$。
• 对于 1,2,4 操作，$1\le x\le 10^9$。
• 对于 4 操作，$1\le y\le 10^9$。
• 保证数据随机。

时间限制：2s。
空间限制：250MB。
::::: ODT 板子题，直接上讲解。
:::::success[ODT 讲解] ODT 由 lxl 发明，在该题诞生，是一种专门处理随机数据且包含覆盖操作的一种暴力数据结构。
我们考虑维护一些连续段，每个连续段内的数都相同，由于本题有比较多的覆盖操作，所以期望复杂度是有保证的。
我们只需要用 set 维护连续段即可。
::::: 然后这道题直接维护即可。
重点在代码。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-24 16:35:51

:::::info[题目基本信息] 考察：数学，博弈论，数位 DP（NOI/NOI+/CTSC）。
题目简介：
$T$ 组数据，每组数据给定 $N,K$，定义正整数对 $(n,k)$ 合法（不合法）为：

• $\forall i\ge 1,(1,i)$ 不合法。
• $\forall n>1,\exist i\in[1,\min(n-1,k)],(n-i,2i)$ 不合法则 $(n,k)$ 合法，否则不合法。

求有多少正整数 $n\le N$，满足 $(n,K)$ 合法。
数据范围：

• $1\le T\le 10^5$
• $1\le N,K\le 10^{18}$

时间限制：1s。
空间限制：180MB。
::::: 齐肯多夫定理相关博弈板子题，引入齐肯多夫定理：
:::::success[齐肯多夫定理讲解] 齐肯多夫定理：$\forall n\in\mathbb Z_+,\exist k\in\mathbb Z_+,\exist\{id_k\}$ 满足：

• $\forall i\in[1,k-1],id_i+1<id_{i+1}$。
• $\displaystyle\sum_{i=1}^kf_{id_i}=n$，其中 $f_i$ 表示斐波那契数列的第 $i$ 项。

::::success[证明] 考虑数学归纳法：
若 $\exist p\in\mathbb Z_+,f_p=n$，则显然成立。
否则，设 $f_p<n<f_{p+1}$，递归 $n-f_p$ 的子问题，容易发现 $f_{p-1}>n-f_p$，所以不会取到相邻的斐波那契数，同时由于数一直在不断减小，所以最终一定能转化成第 $1$ 种情况。
:::: ::::: 对于本题，容易发现先手全取完一定能赢，所以我们不妨钦定先手不能先取完。
对 $n$ 分类讨论：

• $\exist p\in\mathbb Z_+,f_p=n$：
  这时先手必败。 :::::success[证明] 设 $(n-i,2i)$ 为它的后继状态。
• 当 $i\ge f_{p-2}$ 时，后手直接全取完就赢了。
• 在 $n=1$ 时，先手都取不了，必败。
• 在 $n=2$ 时，先手同样必败。
• 在 $i<f_{p-2}$ 的其他情况时，归纳假设后手能在 $f_{p-2}$ 的子问题获胜，然后递归到 $f_{p-1}$ 的子问题，先手唯一希望是取完 $f_{p-1}$，但是不可能，因为后手最后一手取的不超过 $\dfrac{2}{3}f_{p-2}$，由于有定理： $$\frac{4}{3}f_{x}<f_{x+1}$$ ::::success[证明] $$\frac{4}{3}f_x<f_{x+1}\\Leftrightarrow\frac{4}{3}f_x<f_{x-1}+f_x\\Leftrightarrow\frac{1}{3}f_x<f_{x-1}\\Leftrightarrow\frac{1}{3}(f_{x-1}+f_{x-2})<f_{x-1}\\Leftrightarrow\frac{1}{3}f_{x-2}<\frac{2}{3}f_{x-1}\\Leftrightarrow f_{x-2}<2f_{x-1}$$ 显然成立。
  :::: :::::
• 对于其他情况，答案就为 $f_{id_1}$。 :::::success[证明] 先证明 $[1,f_{id_1})$ 的数不合法，这时 $f_{id_1}$ 的子问题后手胜利，套用上面的结论，后面的数均为后手胜利，所以先手必败。
  $f_{id_1}$ 合法的原因也类似。
  ::::: 这时我们直接枚举 $n$ 判断合法性会 TLE，考虑 Fib 位数位 DP。
  设 $dp_{x,0/1,0/1}$ 表示考虑到第 $x$ 位，前面是否选了任何一个 $f_p$，同时上一位选没选。
  转移是平凡的，在 $f_p$ 小于等于 $k$ 的时候后面直接全填 $0$ 就可以得出先手必败的数量（记得要判 $0$）。
  然后容斥以下就行。 时间复杂度为 $\Theta(T\log n)$，空间复杂度为 $\Theta(\log n)$。

code