本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-09 09:56:17

:::::info[闲话]{open} 困难题，怎么有人写题解了。 ::::: :::::info[题目基本信息] 考察：倍增，贪心（省选/NOI-）。
题目简介：
有 $n$ 个城市，相邻两个城市间的距离构成了数列 $\{l_{n-1}\}$，一个人他的油箱最多能装 $m$ 个单位的油，他进行了 $q$ 次行程，对于第 $i$ 次行程，初始时油箱里有 $v_i$ 个单位的油，他要从城市 $s_i$ 跑到城市 $t_i$，每走一个单位长度的距离会消耗一个单位的油，每当他处于一个城市 $j$，它能付出 $a_j$ 的代价购买一个单位的油，询问他想要抵达 $t_i$ 最少需要多少个单位的油。
数据范围：

• $1\le n,q\le 10^6$
• $1\le m\le 10^{18}$
• $\forall i\in[1,n),1\le l_i\le\min(V,10^6)$
• $\forall i\in[1,n],1\le a_i\le 5\times 10^6$
• $\forall i\in[1,m],1\le s_i<t_i\le n$
• $\forall i\in[1,m],0\le v_i\le V$ ::::: 这个题我们先考虑贪心刻画他行程的过程，当他处于一个城市 $s$ 时，找到如果在他这里装满油能跑到的最远的城市，如果在这一段中没有比它的 $p_s$ 更小的城市 $d$（下文简称情况 1），那么我们会令 $d$ 为这段中 $p_d$ 最小的城市中最远的城市（最远是因为这个城市的 $p_s$ 已经很优，我们得让他多跑），否则（下文简称情况 2）我们找到最近的比 $p_s$ 更小的 $d$，跑到 $d$，重复该过程直到跑到终点。
  我们发现可以使用倍增来优化这个过程（存在线段树做法，但是我太菜了不会），具体地，对于前面的预处理，我们设 $\{pos_n\}$ 表示这些城市与城市 $1$ 的距离（同时这也表示这些城市的位置），可以对 $\{l_{n-1}\}$ 求前缀和得到，再设 $r_i$ 在情况 1 表示城市 $i$ 最远能到达的城市，在情况 2 表示城市 $i$ 的后继 $d$，这个容易维护，最远能到达的城市可以双指针求出，后继 $d$ 可以单调栈求出，两者取一个 $\min$ 就是 $\{r_n\}$。
  维护完 $\{r_n\}$ 后设 $nxt_{i,j}$ 表示城市 $i$ 进行 $2^j$ 次跑后会到达哪个城市，根据上述容易求出 $nxt_{i,0}$（区间查询 $p_i$ 最小的城市中最远的城市可以使用 ST 表），倍增容易求得所有的 $nxt_{i,j}$。
  再设 $p_{i,j}$ 表示从城市 $i$ 开始进行 $2^j$ 次跑后加的油能跑到的位置，对于情况 1，我们令 $p_{i,0}\leftarrow pos_i+m$，对于情况 2，我们令 $p_{i,0}\leftarrow pos_{r_i}$，倍增也容易求得所有的 $p_{i,j}$。
  最后我们要算答案，所以我们还需要设 $f_{i,j}$ 表示从城市 $i$ 开始进行 $2^j$ 次跑后所需的油量，初始时我们令 $f_{i,0}\leftarrow (p_{i,0}-pos_i)\cdot a_i$，但是倍增时我们不能直接令 $f_{i,j}\leftarrow f_{i,j-1}+f_{nxt_{i,j-1},j-1}$，这样在 $i$ 跑 $2^{j-1}$ 次触发情况 1 时会有一段距离算重了，这时正确的倍增转移为： $$f_{i,j}\leftarrow f_{i,j-1}+f_{nxt_{i,j-1},j-1}-(p_{i,j-1}-pos_{nxt_{i,j-1}})\cdot a_{nxt_{i,j-1}}$$ 这样我们就做完了所有的预处理，现在我们来回答询问。
  先特判掉 $pos_{t_i}\le pos_{s_i}+v_i$。
  现在我们考虑消去 $v_i$ 的影响，这个非常妙妙妙，注意到这个答案就是在 $v_i=0$ 时 $pos_{s_i}$ 到 $pos_{t_i}$ 的答案减去在 $v_i=0$ 时 $pos_{s_i}$ 到 $pos_{s_i}+v_i$ 的答案，这样就消去了 $v_i$ 的影响。
  在倍增求 $v_i=0$ 时的答案时，我们不断跳逼近（但不到达，因为到达后可能后面会跟随一小段距离导致算多，没算的这一部分最后算上就好啦），与倍增过程所维护的信息类似，就不过多赘述。
  最终时间复杂度为 $\Theta((n+m)\log n)$，空间复杂度为 $\Theta(n\log n)$。

code
同机房大佬 KSCD_ 实现的线段树做法也在其中（模拟赛赛时代码）。

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

:::::info[题目基本信息] 考察：构造，图论（省选/NOI-）。
题目简介：
你有 $n\times m$ 的网格板，上面有 $\dfrac{nm-1}{2}$ 个大小为 $1\times 2$ 的木板和一个空位，你每次操作可以选择空位相邻的一个木板拿出，并通过旋转或平移使得其覆盖原空位，给定初状态和末状态，要求通过操作把初状态转化为末状态，操作数不得超过 $8\times 10^6$。
数据范围：

• $1\le n,m\le 2000$
• $n,m$ 均为奇数。
  ::::: 这个题如果我们令一个木板相当于一条边，那么整个网格板就是整张图的最大匹配，现在我们令这两张图做异或，定义图的异或如下（这个应该有个名词但我忘了）：
  :::::info[图的异或] 有图 $A,B$，那么 $G=A\oplus B=\{(u,v)|[(u,v)\in A]+[(u,v)\in B]=1\}$。
  ::::: 容易发现由于原两图均为匹配，故原图上每个点的度最多为 $1$，异或后度最多为 $2$ 且仅有最多 $2$ 个点度为 $1$，故最终异或图是由一条链和一堆环组成。
  我们的思路就是在跑这一条链的过程中找到没有跑的环，然后跑过去进行交换，再跑回来。
  具体地，我们跑一个 DFS，DFS 过程中先找到他所在的链，然后在其他方向找到别的没有被找链的点进行 DFS，最后再走找到的链。
  DFS 极其不标准的伪代码如下：

DFS(x,y):
  if (x,y) has arrived: return
  find-the-chain-of(x,y)
  for (tx,ty) is near (x,y):
    if (tx,ty) has not been looked for the chain:
      move to (tx,ty)
      DFS(tx,ty)
  let (tx,ty) be the next node of (x,y) in the chain
  DFS(tx,ty)

那么现在我们该如何找到这条链呢？
我们现在的 $(x,y)$ 是空白格，那么我们可以通过末状态推出下一个点，再对下一个点通过初状态推出下下个点，移动木板并开始递归即可。
递归到被递归的点自然就不用递归了。
由于转移到环的这段过程中已经把木块移过去导致与终状态产生差异就不必在进行撤销操作的动作了。
这样我们就做完了此题。
容易发现构造次数不超过 $2nm$。
时空复杂度均为 $\Theta(nm)$。

code

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

:::::info[题目基本信息] 考察：构造（$3000$）。
题目简介：
给定非正整数序列 $\{a_n\}$，有操作：

• 选择 $x,y\in[1,n]$，使得 $a_x\le a_y$，同时令 $a_y\leftarrow a_y-a_x,a_x\leftarrow 2a_x$。

要求一系列操作完成后序列中恰好有两个数非 $0$，要求构造一组操作，操作数不得超过 $10^6$，无解给出 -1。
数据范围：

• $1\le n\le 1000$
• $0\le \sum a_i\le 10^6$ ::::: 显然，操作不会使序列中 $0$ 的个数减少，同时也不会使 $0$ 的个数一次性减少的个数超过 $1$，所以在序列非 $0$ 个数小于 $2$ 时便无解。
  我们先考虑让两个数来回操作的情况，但是这样很快就寄了，比如我们无法通过操作把 $1,2$ 两个数中的一个变为 $0$。
  那我们再考虑 $3$ 个数内部操作，我们先考虑特殊情况。
  钦定操作的三个数为 $a_x.a_y,a_z$，且 $a_x\le a_y\le a_z$。
  容易发现，在 $a_x\mid a_y$ 时，我们可以通过对于 $k=\dfrac{a_y}{a_x}$ 二进制下的从低到高的每一位进行分讨（设目前处理到了第 $i$ 位）：
• 当第 $i$ 位为 $1$ 时，操作 $(x,y)$。
• 当第 $i$ 位为 $0$ 时，操作 $(x,z)$。

这时我们就能把 $a_y$ 清空成 $0$，且由于 $a_z$ 的减少量小于 $a_y$ 的减少量，故 $a_z$ 不会被清零，这样我们就将一个数清为 $0$ 了。
但是在 $a_x\nmid a_y$ 时又该如何呢？
令 $p=a_y\bmod a_x$，最终 $a_y\leftarrow p$，这时将 $a_x,a_y,a_z$ 重新排序 $a_y$ 一定会被被排序到 $a_x$ 的位置上，成为 $a'_x$，这时 $a'_x=p<a_x$，那么这样下去早晚会产生 $0$。
这样我们就有了一种构造方案，现在我们来观察一下复杂度。
容易发现，令 $a_x\leftarrow a_y\bmod a_x$ 的一轮操作构造复杂度为 $\Theta(\log V)$ 次。同时由于有结论（下文钦定 $a\ge b$）：
$$a\bmod b<\frac{a}{2}$$ :::::success[证明] 当 $b>\dfrac{a}{2}$ 时，$a\bmod b=a-b<a-\dfrac{a}{2}=\dfrac{a}{2}$。
当 $b\le\dfrac{a}{2}$ 时，$a\bmod b<b\le\dfrac{a}{2}$。
::::: 这样轮数大概是在 $\Theta(\log V)$ 量级的，但是这个东西和辗转相除法等价在哪？？？？故本人目前不会严谨的证明。
这样构造复杂度大约是在 $\Theta(n\log^2 V)$ 的，反正能过。
时间复杂度为 $\Theta(n\log^2 V)$，空间复杂度为 $\Theta(n)$。

code

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

:::::info[题目基本信息] 考察：图论，线段树，扫描线（$2819$）。
题目简介：
给定一个二分图 $G$，有 $n$ 个左部点和 $m$ 个右部点，第 $i$ 个右部点的权值为 $i$，同时给定序列 $\{l_n\},\{r_n\}$，表示第 $i$ 个左部点会和权值 $x$ 满足 $x\le l_i\lor x\ge r_i$ 的右部点连一条边，现在你可以增加一些右部点并任意钦定他们的权值使得该二分图的最大匹配为 $n$，问最少添加几个右部点。
数据范围：

• $1\le n,m\le 2\times 10^5$
• $\forall i\in[1,n],0\le l_i<r_i\le m+1$ ::::: 显然，本题的答案等价于 $n-\nu(G)$。
  通过尝试众多算法后无果，考虑引入 Hall 定理：
  :::::success[Hall 定理]{open} 一个二分图（$G=(V_1,V_2,E)$，钦定 $|V_1|\le|V_2|$），设该二分图的最大匹配为 $\nu(G)$，则 $\nu(G)=|V_1|$ 当且仅当：$\forall V\subseteq V_1,|N_G(V)|\ge|V|$，其中 $N_G(V)$ 表示在图 $G$ 中 $V$ 的邻居点集合。
  ::::: :::::success[证明] 我去他的哪个是充分哪个是必要来着。
• 必要性（后者是前者的必要条件）：
  若 $\exists V\subseteq V_1,|N_G(V)|<|V|$，那么 $V$ 的最大匹配小于 $|V|$，同时由于，每次 $V$ 新增一个点的过程中最大匹配最多增加 $1$，故 $\nu(G)<|V_1|$，与条件矛盾，必要性得证。
• 充分性（后者是前者的充分条件）：
  若存在二分图 $\nu(G)<|V_1|$ 但满足条件 $\forall V\subseteq V_1,|N_G(V)|\ge|V|$，那么一定有一个左部点不在匹配中，由于满足后者的条件，那么他一定有所连的右部点与其他左部点相连，考虑将这些左部点和原点一起考虑，由于后者条件仍能找到未加进来的右部点，这样不断递归就形成了一条增广路，将其增广可以得到大小为 $|V_1|$ 的匹配，与假设矛盾，充分性得证。

证毕。
::::: Hall 定理还有一条推论：
:::::success[Hall 定理推论]{open} （引用 Hall 定理内的定义）
$$\nu(G)=|V_1|-\max_{V\subseteq V_1}(|V|-|N_G(V)|)$$ ::::: :::::success[证明] 还是开拆成不等式。

• $\displaystyle\nu(G)\le|V_1|-\max_{V\subseteq V_1}(|V|-|N_G(V)|)$：
  对于一子集 $V\subseteq V_1$ 且 $|V|\ge|N_G(V)|$，该子集内未被匹配的点最少为 $|V|-|N_G(V)|$ 个，那么由于左部点每增加一个点左部点未被匹配的点一定不会减少，所以该二分图未被匹配的点最少为 $\displaystyle\max_{V\subseteq V_2}(|V|-|N_G(V)|)$ 个，小于等于号得证。

• $\displaystyle\nu(G)\ge|V_1|-\max_{V\subseteq V_1}(|V|-|N_G(V)|)$：
  考虑构造一个新图 $G'=(V_1,V_2',E')$，其中：

  • $V_2'=V_2\cup D$，其中 $D$ 满足：$|D|=\displaystyle\max_{V\subseteq V_1}(|V|-|N_G(V)|),V_2\cap D=\arnothing$。
  • $E'=E\cup\{(u,v)|u\in V_1,v\in D\}$。

  对于一子集 $V\subseteq V_1$，它在 $G$ 上的邻居点集 $N_{G'}(V)=N_G(V)\cup D$，那么： $$|N_{G'}(V)|=|N_G(V)\cup D|=|N_G(V)|+\max_{V\subseteq V_1}(|V|-|N_G(V)|)$$ 注意到 $|V|\le|N_G(V)|+\displaystyle\max_{V\subseteq V_1}(|V|-|N_G(V)|)=|N_{G'}(V)|$，那么由 Hall 定理可知，$\nu(G')=|V_1|$。
  现在将这 $\displaystyle\max_{V\subseteq V_1}(|V|-|N_G(V)|)$ 个点逐一删去，容易发现每次最大匹配最多减少 $1$，那么我们就得到：
  $$\nu(G)\ge|V_1|-\max_{V\subseteq V_1}(|V|-|N_G(V)|)$$ 大于等于号得证。

原命题得证。
::::: 将引理代入得到本题答案为 $\displaystyle\max_{V\subseteq V_1}(|V|-|N_G(V)|)$，在本题中 $\displaystyle|N_G(V)|=\bigcup_{u\in V}[1,l_u]\cup[r_u,m]$，其中 $[l,r]$ 在 $l>r$ 时表示 $\arnothing$。
但是区间的并（还是两段）并不好做，所以我们考虑容斥成区间的交，容易得到 $\displaystyle\bigcup_{u\in V}[1,l_u]\cup[r_u,m]=m-\bigcap_{u\in V}(l_u,r_u)$。
现在考虑枚举交集，但是你好像忘了什么……

• 交集为空集：
  这时需要满足条件 $\displaystyle\max_{i=1}^nl_i\ge\min_{i=1}^nr_i$，最终答案就是 $|V|-m$，最大即 $n-m$。
• 交集非空：
  设交集的开左端点为 $L$，开右端点为 $R$，那么开左端点为 $L$ 的答案就是 $\displaystyle\max_{R=L+1}^m((\sum_{i=1}^n[l_i\le L\land r_i\ge R])+R-L-1-m)$。 这个可以先对 $(l_i,r_i)$ 按第一关键字为 $l_i$ 升序，第二关键字为 $r_i$ 降序的顺序排序，然后就可以上扫描线加线段树做这题了。

然后就做完了。
时间复杂度为 $\Theta(n\log n+n\log m+m)$，空间复杂度为 $\Theta(n+m)$。

code

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

:::::info[闲话] LCA Project 几乎全机房人都被这道题肘飞了…… ::::: :::::info[题目基本信息] 考察：倍增（省选/NOI-）。
题目简介：
一个平面上初始时有两个点，坐标给定，且两点间有一条道路，长度为两点的欧几里得距离。
现在你要进行 $n$ 次操作，操作分为两种：

1. 新增一个点，坐标为 $(x,y)$，同时会向 $u,v$ 两点连边，长度也为欧几里得距离，但保证 $u,v$ 两点已有边相连。
2. 查询 $u,v$ 间最短路。

数据范围：

• $1\le n\le 10^5$
• $0\le x,y\le 10^6$
• 保证操作的点都存在，且两两坐标不相同。
  ::::: 这个题一个观察是如果直接跑最短路那么复杂度是不可接受的，一个考虑是通过某种方式把树建出来然后倍增跳求 LCA。
  显然如果直接对点是无法建树的，同时也无法删去任何一条边，但是我们观察到连边方式很特别，所以我们考虑对所连的边建树。
  具体地，每次连的边 $(x,u),(x,v)$ 会和原来的边 $(u,v)$ 形成一个三角形，所以我们考虑令 $(x,u)$ 和 $(x,v)$ 分别和 $(u,v)$ 连边，容易发现最终连出来的就是一棵树。（为方便区分原来的边叫做原图边，后来建树用的边叫做建树边）
  :::::success[证明] 初始时有一条原图边和 $0$ 条建树边，每次 1 操作会增加 $2$ 条原图边和 $2$ 条建树边，同时该图容易归纳证明一直联通，故该图一直为树。
  ::::: 由于本题中的边权都是欧几里得距离，他是两点间的最短距离，那么一个观察就是 $u$ 到 $v$ 走的路径一定是 $u$ 新增时所连的原图边和 $v$ 的新增时所连的原图边在树上的路径，同时由于发现 $u$ 和 $v$ 的分别的这两条新增时所连的原图边在树上共用父亲，故取哪条原图边效果均相同。
  实现上，我们可以对每个点存储两条新增时所连的原图边和坐标，对于每条原图边记录所连的两个点（可以使用指针）、在树上的深度以及树上的倍增数组，对于倍增数组的每一层我们都维护将会跳到的原图边（同样用指针）以及一矩阵表示跳的边和将会跳到的原图边的分别的任意一个端点间的距离，这个预处理也容易维护，倍增查询也是板子，不过有几个需要注意的点：
• 在两个原图边一起往上跳跳到即将相遇时，先别急着跳完，这时有可能两个点已经有公共端点了，记得把它算到贡献里。
• 如果你使用了指针，那么在用的时候一定要注意不要访问 NULL 指针内的元素，以及在别的函数内修改指针时可能会需要再次求指针，当然了如果你不想用指针后面会给一份 KSCD_ 的无指针实现方式。

结束。
时空复杂度均为 $\Theta(n\log n)$。

code（指针）
code（无指针）（这一份里有 freopen，是赛时代码）

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-14 17:27:04

:::::info[题目基本信息] 考察：贪心，哈希 Hashing，Ad-hoc（省选/NOI-）。
题目简介：
给定一个 $n\times m$ 的仅由小写英文字母组成的网格图，现在你需要构造一个任意长度的木板，上面每一个都有一个小写英文字母，你可以左右或上下放置该木板，但是不能调转该木板的方向，你现在需要用这个木板铺满网格图，问所有可能的木板长度有哪些。
数据范围：

• $1\le n,m\le 1000$ ::::: 容易发现所有可能的木板长度 $l$ 必须满足 $l\mid n$ 或 $l\mid m$。
  为方便和符合个人习惯本命题证明内使用 $0$ 开始的编号，本命题证明后实现使用 $1$ 开始的编号。
  :::::success[证明] 考虑将格子 $(i,j)$ 染色成 $(i+j)\bmod l$，那么这些木板每一个都覆盖 $l$ 个不同的颜色，那么每种颜色都应该有 $\dfrac{nm}{l}$ 种，那么 $l\nmid nm$ 时显然不合法。
  设现在我们要求颜色 $c$ 的格子数量（$c\in[0,l)$），我们容易列出式子：
  $$F(c)=\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}[i+j\equiv c\pmod l]$$ 容易发现这个函数在 $[0,l)$ 内单调不升，那么我们现在只需证明：
  $$\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}[i+j\equiv 0\pmod l]=\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}[i+j\equiv l-1\pmod l]\\Leftrightarrow\sum_{i=0}^{n-1}\lfloor\frac{m-i\bmod l}{l}\rfloor+1=\sum_{i=0}^{n-1}\lfloor\frac{m-(l-1-i\bmod l)}{l}\rfloor+1\\Leftrightarrow\sum_{i=0}^{n-1}\lfloor\frac{m-i\bmod l}{l}\rfloor=\sum_{i=0}^{n-1}\lfloor\frac{m-(l-1-i\bmod l)}{l}\rfloor$$ 这个式子容易发现只在 $l\mid n$ 或 $l\mid m$ 时成立，证毕。
  ::::: 现在我们考虑对于格子 $(1,1)$，它被覆盖时要么向下覆盖要么向右覆盖，那么可能的木板样式只有 $\Theta(\sqrt n+\sqrt m)$ 种，我们可以尝试在 $\Theta(nm)$ 的时间复杂度内判定一个木板样式是否合法。
• 当整个网格字符都相同时，任意 $n$ 或 $m$ 的因数长度都满足条件。
• 否则木板样式内的字符一定互不相同，这时我们考虑贪心地让每个木板向右扩展，具体地，在一个格子左侧格子和上侧格子已经被扩展的基础上，能向右扩展就向右扩展。 :::::success[证明] 如果设 $(x,y)$ 为当前处理的格子，然后 $(x,y)$ 到 $(x,y+k)$ 都向下扩展了（$k\in [0,l)$），同时 $(x,y+k+1)$ 往后会向右扩展，那么木板样式会有长度为 $k+1$ 的 border，且前 $k+1$ 格字符均相同，故木板样式内的字符均相同，与假设矛盾。 ::::: 这样我们就证明完毕了我们贪心策略的正确性，现在我们需要通过一种方式 $\Theta(nm)$ 解决这个问题，这个比较简单，考虑记 $vis_{i,j}$ 表示 $(i,j)$ 是否被扩展过，$flag_{i,j}$ 表示 $(i,j)$ 的右侧一定距离内是否有被扩展过的点，容易在 $\Theta(nm)$ 内维护。

这样我们就做完了这道题。
时间复杂度为 $\Theta(nm(\sqrt n+\sqrt m))$，空间复杂度为 $\Theta(nm)$。

code

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

:::::info[闲话] 计数题怎么这么难。
::::: :::::info[题目基本信息] 考察：组合数学，动态规划 DP，数学（$2600$）。
题目简介：
在一个数轴上，有 $1$ 到 $n$ 的 $n$ 个位置，现在你要在 $m$ 个位置种上树并将他们砍倒，砍倒后的树可以钦定他们向左倒或向右倒，给定常数 $k$，若该树位置为 $x$，则向左倒会覆盖 $[x-k,x]$ 的所有位置，向右倒会覆盖 $[x,x+k]$ 的所有位置，问有多少种不同的种树方案使得他们能在砍倒后满足一个位置不被覆盖两次（对 $998244353$ 取模），方案不同当且仅当存在一个位置一种方案里种了树而另一种方案没有。
数据范围：

• $1\le m,k\le n\le 3\times 10^5$ ::::: 先考虑如何决策这些树是如何倒下的，这就是一个经典贪心，优先让每个树向左倒，倒不下在向右倒。
  那么我们考虑朴素 DP，设 $dp_{i,j}$ 表示种了前 $i$ 棵树，最后一棵树最后覆盖的位置为 $j$，初始时 $dp_{0,0}=0$。
  那么容易得到转移（对于 $dp_{i,j}$ 向后转移的过程）：
• $\forall j_2\in[j+k+1,j+2k],dp_{i+1,j_2}\leftarrow 2dp_{i,j}$，即既能向左倒又能向右倒。
• $\forall j_2\in[j+2k+1,+\infty),dp_{i+1,j_2}\leftarrow dp_{i,j}$，即只能向左倒。

暴力转移可以得到 $\Theta(n^2m)$ 做法，利用数据结构优化可以得到 $\Theta(nm\log n)$ 做法，然后就没有出路了。

我们考虑使用一些组合数学知识，设 $\{p_m\}$ 表示在种树的过程中，每前 $i$ 棵树时最后一棵树的最后覆盖位置构成的序列，同时令 $p_0=0$，那么由上面的转移方程可以得到 $\forall i\in[1,m],p_i-p_{i-1}\ge k+1$，同时当 $p_i-p_{i-1}\le 2k$ 时会有 $2$ 的贡献，那么我们可以先在 $n-m(k+1)$ 个位置里选 $m$ 个不降的位置，然后在他们前面分别补 $k+1$ 个位置，这样我们就消去了 $p_i-p_{i-1}\ge k+1$ 的限制条件，贡献条件 $p_i-p_{i-1}\le 2k$ 转变成 $p_i-p_{i-1}\le k-1$。
现在我们考虑设 $f_i$ 表示这 $m$ 个位置里面恰好有 $i$ 个满足 $p_i-p_{i-1}\ge k$ 的位置的选择方案数，但是这个东西并不好直接求，所以我们考虑再设 $g_i$ 表示这 $m$ 个位置里面钦定其中 $i$ 个满足 $p_i-p_{i-1}\ge k$ 的位置的选择及钦定方案数，这个容易用组合数表示出来，首先钦定会带来 $\dbinom{m}{i}$ 的贡献，然后我们需要在 $n-m(k+1)$ 的序列选出 $m$ 个不降位置，其中一些位置中间需要相隔至少 $k$ 个位置，我们考虑也把这 $k$ 个位置扔掉，变成在 $n-m(k+1)-ik$ 的序列中选出 $m$ 个不降位置，这就是经典插板法，最终会带来 $\dbinom{n-m(k+1)-ik+m}{m}$ 的贡献。
综上我们得到：
$$g_i=\binom{m}{i}\binom{n-m(k+1)-ik+m}{m}$$ 同时由于 $f_i$ 和 $g_i$ 的定义的联系，我们得到：
$$g_i=\sum_{j=i}^m\binom{j}{i}f_j$$ 马上可以反演出：
$$f_i=\sum_{j=i}^m(-1)^{j-i}\binom{j}{i}g_j$$ 由于 $f_i$ 的定义最终答案 $ans$ 为：
$$ans=\sum_{i=0}^m2^{m-i}f_i$$ 把上面的式子堆起来可以得到：
$$\begin{aligned}ans&=\sum_{i=0}^m2^{m-i}\sum_{j=i}^m(-1)^{j-i}\binom{j}{i}\binom{m}{j}\binom{n-m(k+1)-jk+m}{m}\&=\sum_{i=0}^m\sum_{j=i}^m2^{m-i}(-1)^{j-i}\binom{j}{i}\binom{m}{j}\binom{n-m(k+1)-jk+m}{m}\&=\sum_{j=0}^m\binom{m}{j}\binom{n-m(k+1)-jk+m}{m}\sum_{i=0}^j2^{m-i}(-1)^{j-i}\binom{j}{i}\&=2^m\sum_{j=0}^m\binom{m}{j}\binom{n-m(k+1)-jk+m}{m}\sum_{i=0}^j2^{-i}(-1)^{j-i}\binom{j}{i}\&=2^m\sum_{j=0}^m\binom{m}{j}\binom{n-m(k+1)-jk+m}{m}\sum_{i=0}^j(\frac{1}{2})^i(-1)^{j-i}\binom{j}{i}\&=2^m\sum_{j=0}^m\binom{m}{j}\binom{n-m(k+1)-jk+m}{m}(-\frac{1}{2})^{j}\&=2^m\sum_{j=0}^m\binom{m}{j}\binom{n-m(k+1)-jk+m}{m}(-1)^j2^{-j}\&=\sum_{j=0}^m\binom{m}{j}\binom{n-m(k+1)-jk+m}{m}(-1)^j2^{m-j}\end{aligned}$$ 爽飞了，可以线性计算了。

时空复杂度均为 $\Theta(n+m)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-16 17:12:37

:::::info[题目基本信息] 考察：组合数学，动态规划 DP（$2780$）。
题目简介：
给定 $\{a_n\}$，求有多少 $\{b_n\}$ 满足（对 $998244353$ 取模）：

• $\forall i\in[1,n],b_i\in[1,n]$
• $\forall i\in[1,n],\sum_{j=1}^n[b_j=i]\le a_i$
• $\forall i\in[1,n],\sum_{j=1}^n[b_j=b_i]\le a_i$

数据范围：

• $1\le n\le 500$
• $\forall i\in[1,n],1\le a_i\le n$ ::::: 通过尝试我们发现朴素地对位置 DP 或者连续段 DP 都是不行的，所以我们换一种思路，考虑对限制进行 DP，那么我们注意到一个优美的性质，如果我们按一个数在 $\{b_n\}$ 的出现次数降序决策，那么它们之间的影响和干扰不大，所以我们尝试这条道路。
  具体地，设 $f_{i,j,k}$ 表示考虑到所有在 $\{b_n\}$ 中出现次数不低于 $i$ 的数，一共有 $j$ 个，一共出现了 $k$ 次，考虑枚举出现次数恰好为 $i$ 的数的个数为 $l$，那么我们需要转移到 $f_{i-1,j+l,k+(i-1)l}$ ，设 $t_i=\displaystyle\sum_{j=1}^n[a_j\ge i]$，那么我们需要在 $t_{i-1}-j$ 种还没填的数里面选 $l$ 种数进行一个填，然后在 $t_{i-1}-k$ 个位置里选 $(i-1)l$ 个进行一个填，然后排列一下顺序，所以最终的转移方程式为：
  $$f_{i-1,j+l,k+(i-1)l}\leftarrow \binom{t_{i-1}-j}{l}\binom{(i-1)l}{l,l,\dots,l}\binom{t_{i-1}-k}{(i-1)l}f_{i,j,k}$$ 这样的话正确性是有保证的，复杂度是多少呢？
  容易发现 $j,l$ 都是 $\dfrac{n}{i}$ 级别，那么复杂度满足这样一个式子，然后我们将其推导：
  $$\begin{aligned}\sum_{i=1}^n\sum_{j=1}^{\frac{n}{i}}\sum_{k=1}^n\sum_{l=1}^{\frac{n}{i}}1&=\sum_{i=1}^n\sum_{j=1}^{\frac{n}{i}}\sum_{k=1}^n\frac{n}{i}\&=\sum_{i=1}^n\frac{n^3}{i^2}\&=n^3\sum_{i=1}^n\frac{1}{i^2}\end{aligned}$$ 那么 $\displaystyle\sum_{i=1}^n\frac{1}{i^2}$ 是多少呢？
  :::::success[关于上式结果为常数的说明] 有个定理是 $\displaystyle\sum_{i=1}^{\infty}\frac{1}{i^2}=\frac{\pi^2}{6}$，但是关于它的证明太魔怔，所以我们不要用上面的定理。
  注意到我们不需要太精确，所以我们可以适当放缩：
  $$\begin{aligned}\sum_{i=1}^n\frac{1}{i^2}&=1+\sum_{i=2}^n\frac{1}{i^2}\&\le1+\sum_{i=2}^{n}\frac{1}{i(i-1)}\&=1+\sum_{i=2}^n\frac{1}{i-1}-\frac{1}{i}\&=1+\frac{1}{1}-\frac{1}{n}\&<2\end{aligned}$$ 所以这个东西只是常数复杂度。
  ::::: 综上，时空复杂度均为 $\Theta(n^3)$。

code

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

:::::info[题目基本信息] 考察：动态规划 DP（NOI/NOI+/CTSC）。
题目简介：
给定 $n$ 以及 $\{a_n\},\{b_n\}$，$q$ 次询问，每次给定 $l,r$，求：
$$(\sum_{S\subseteq\bigcup_{i=1}^n\{i\},|S|\in[l,r]}[\exist\{p_n\}\in\{\{x_n\}|\forall i\in[1,n],x_i\in[1,n]\land\forall i,j\in[1,n],i\ne j,x_i\ne x_j\},\forall i\in[1,n],[i\in S]=[a_i>b_{p_i}]])\bmod 998244353$$ 数据范围：

• $1\le n\le 5000$
• $\forall i\in[1,n],1\le a_i,b_i\le 2n$
• $\forall i,j\in[1,n],a_i\ne b_j$
• $\forall i,j\in[1,n],i\ne j,a_i\ne a_j$
• $\forall i,j\in[1,n],i\ne j,b_i\ne b_j$
• $1\le q\le n+1$
• $0\le l\le r\le n$

时间限制：1.5s。
空间限制：1GB。
::::: 计数题大部分时候会经历转化问题、发掘性质，判定合法，计算答案四个过程（不要把这四个过程完全割裂，有时算答案时也会出现转化，转化时顺便发掘了性质和判定，需要巧妙地选择进行哪一步），虽然一般这前三个部分一般不难但也许会给我们做 DP 和计数提供思考方向。一个好的例子是 CF2150D，在这道题中这三个过程体现得淋漓尽致。
我们先来暴力。

Part 1：转化问题：

这一步还是比较关键的。
贪心地想，如果 $S$ 中的元素能够大于 $\{b_n\}$ 中的元素，那么肯定是大于了 $\{b_n\}$ 中的前 $|S|$ 个元素，不在 $S$ 中的元素同理。
那么我们先设 $S^{-1}=\complement_{\bigcup_{i=1}^n\{i\}}S$，对 $\{a_n\}$ 和 $\{b_n\}$ 升序排序，同时也令 $S$ 和 $S^{-1}$ 转变成一个有序数列，以编号大小升序排序，那么 $S$ 合法的条件转化为：

• $\forall i\in[1,|S|]，a_{S_i}>b_i$
• $\forall i\in[1,|S^{-1}|],a_{S^{-1}i}<b{i+|S|}$

Part 3：判定合法：

根据贪心策略易证，上面的条件就是 $S$ 合法的充要条件。

Part 4：计算答案：

重头戏来了。
考虑枚举 $|S|$，设 $f_{i,j}$ 为考虑到第 $i$ 个数，有 $j$ 个数在 $S$ 中的合法 $S$ 方案数，根据上述容易得到转移方程：
$$f_{i,j}=[a_i>b_j]f_{i-1,j-1}+[a_i<b_{|S|+i-j}]f_{i-1,j}$$ 这时 $f_{n,|S|}$ 就是 $ans_{|S|}$，对它求前缀和就可以做到 $\Theta(n^3+q)$，过不了，考虑优化。

不要把这四个过程完全割裂，有时算答案时也会出现转化，转化时顺便发掘了性质和判定，需要巧妙地选择进行哪一步。

Part 1：转化问题：

由于原条件中含有 $|S|$，考虑消掉 $|S|$，那么我们可以转化为：

• $\forall i\in[1,|S|]，a_{S_i}>b_i$
• $\forall i\in[1,|S^{-1}|],a_{S^{-1}{|S^{-1}|-i+1}}<b{n-i+1}$

Part 4：计算答案：

我们现在消去了 $|S|$，就可以只进行 $\Theta(1)$ 次 DP，同时由于原条件中两个条件互相独立，所以我们考虑对前缀和后缀分别 DP。
更加具体地，对前缀 DP 时设 $f_{i,j}$ 表示考虑到了长度为 $i$ 的前缀，有 $j$ 个元素在 $S$ 中的 $S$ 方案数，容易得出状态转移方程：
$$f_{i,j}=f_{i-1,j}+[a_i>b_j]f_{i-1,j-1}$$ 同样的，设出 $g_{i,j}$ 的状态为考虑到了长度为 $i$ 的后缀，有 $j$ 个元素不在 $S$ 中的 $S$ 方案数，并得出状态转移方程：
$$g_{i,j}=g_{i+1,j}+[a_i>b_{n-j+1}]g_{i+1,j-1}$$ 现在，我们求出了 $f_{i,j}$ 和 $g_{i,j}$，考虑如何计算 $\{ans_n\}$。

Part 1：转化问题：

显然我们不能直接找一个位置 $k$ 直接拼起来 $f_{k,j}$ 和 $g_{k+1,j}$，因为可能前缀的一些不在 $S$ 中的和后缀的一些在 $S$ 中的不合法，所以我们考虑找到一个符合条件的 $k$。
由于现在 $|S|$ 已知，我们希望条件中出现 $|S|$（以及 $|S^{-1}|$），所以我们继续转化条件：

• $\forall i\in[1,|S|]，a_{S_{|S|-i+1}}>b_{|S|-i+1}$
• $\forall i\in[1,|S^{-1}|],a_{S^{-1}i}<b{i+|S|}$

容易得到位置 $k$ 合法的条件：

• $\forall i\in[1,k]\cap S^{-1},a_i<b_{|S|+p}$，其中 $p$ 是一个未知的正整数。
• $\forall i\in[k+1,n]\cap S,a_i>b_{|S|-p}$，其中 $p$ 是一个未知的非负整数。

Part 2：发掘性质：

我们注意到当 $p\ge 0$ 时，$b_{|S|-p}\le b_{|S|}\le b_{|S|+p}$，所以条件弱化为：

• $\forall i\in[1,k]\cap S^{-1},a_i<b_{|S|}$
• $\forall i\in[k+1,n]\cap S,a_i>b_{|S|}$

所以我们得到 $k$ 就是最大的整数满足 $a_i<b_{|S|}$，这个可以使用双指针或者二分得到。

Part 4：计算答案：

最终，我们终于要计算 $\{ans_n\}$ 了。
容易得到：
$$ans_p=\sum_{i=\max(0,p+k-n)}^{\min(k,p)}f_{k,i}g_{k+1,n-p-k-i}$$ 其中，所有上界和下界均为了保证 $f$ 和 $g$ 存在。
然后做个前缀和就做完了。
时间复杂度为 $\Theta(n^2+q)$，空间复杂度为 $\Theta(n^2)$。

code

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

:::::info[题目基本信息] 考察：ST 表，前缀和，线段树，可持久化线段树，分治（省选/NOI-）。
题目简介： 给定 $n,p$ 以及 $\{h_n\},\{a_n\}$，求有多少个整数对 $(l,r)$ 满足：

• $1\le l,r\le n$
• $\displaystyle\forall k\in[l,r],(\sum_{i=l}^r[i\ne k]\max(0,h_i-a_i))+\max(0,a_i-h_i)\ge p(\sum_{i=l}^r[i\ne k]\max(0,a_i-h_i)+\max(0,h_i-a_i))$

数据范围：

• $1\le n\le 2\times 10^5$
• $1\le p\le 100$
• $\forall i\in[1,n],0\le h_i,a_i\le 10^6$

时间限制：5s。
空间限制：2GB。
::::: 首先，贪心地想，选取的 $k$ 一定满足 $h_k-a_k$ 在 $[l,r]$ 中最大，如果 $\forall i\in[l,r],h_i\le a_i$ 那么不会交换，同时这个区间不会产生贡献。
考虑进行启发式分治，每次选取 $h_k-a_k$ 最大的 $k$，向左右两边分治，同时查询经过 $k$ 的区间的贡献，找到这个 $k$ 显然可以使用 ST 表实现。
现在最大的问题就是怎么计算经过 $k$ 的区间的贡献，先对原条件转化：
$$(\sum_{i=l}^r[i\ne k]\max(0,h_i-a_i))+\max(0,a_i-h_i)\ge p((\sum_{i=l}^r[i\ne k]\max(0,a_i-h_i))+\max(0,h_k-a_k))\\Leftrightarrow (\sum_{i=l}^r[i\ne k]\max(0,h_i-a_i))-(p\sum_{i=l}^r[i\ne k]\max(0,a_i-h_i))\ge p\max(0,h_i-a_i)-\max(0,a_k-h_k)$$ 由于 $h_k>a_k$ 才能产生贡献，所以我们就可以继续转化：
$$(\sum_{i=l}^r[i\ne k]\max(0,h_i-a_i))-p(\sum_{i=l}^r[i\ne k]\max(0,a_i-h_i))\ge p\max(0,h_i-a_i)-\max(0,a_i-h_i)\\Leftrightarrow(\sum_{i=l}^r[i\ne k]\max(0,h_i-a_i))-(p\sum_{i=l}^r[i\ne k]\max(0,a_i-h_i))\ge p(h_k-a_k)$$ 令 $b_i=h_i-a_i$，得到：
$$(\sum_{i=l}^r[i\ne k]\max(0,h_i-a_i))-p(\sum_{i=l}^r[i\ne k]\max(0,a_i-h_i))\ge p(h_k-a_k)\\Leftrightarrow(\sum_{i=l}^r[i\ne k]\max(0,b_i))-p(\sum_{i=l}^r[i\ne k]\max(0,-b_i))\ge pb_k\\Leftrightarrow(\sum_{i=l}^r\max(0,b_i))-p(\sum_{i=1}^r\max(0,-b_i))\ge pb_k$$ 前面这坨可以使用前缀和维护。具体地，设 $\displaystyle sum_i=\sum_{j=1}^i\max(0,b_i)-p\max(0,-b_i)$，那么原式转化为：
$$(\sum_{i=l}^r\max(0,b_i))-p(\sum_{i=1}^r\max(0,-b_i))\ge pb_k\\Leftrightarrow sum_r-sum_{l-1}\ge pb_k$$ 现在这坨看起来就非常舒服，我们重新理一下我们要干什么：统计整数对 $(L,R)$ 的个数，满足：

• $l\le L\le k\le R\le r$

• $sum_R-sum_{L-1}\ge pb_k$

• 当 $k-l\le r-k$ 时，我们枚举 $L$，对 $R$ 的限制条件变为：

  • $k\le R\le r$
  • $sum_R\ge sum_{L-1}+pb_k$

  这就是个二维数点问题，可以使用离线线段树或者在线主席树实现，我使用了主席树。

• 当 $k-l>r-k$ 时，我们枚举 $R$，统计方式同理。

这样我们就做完了这道题。
时间复杂度为 $\Theta(n\log^2 n)$，空间复杂度为 $\Theta(n\log n)$。
:::::success[对启发式分治时间复杂度的一点说明] 启发式合并的复杂度我们都知道，是 $\Theta(n\log n)$ 的，启发式分治就相当于启发式合并的逆过程，复杂度显然相同。 :::::