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

:::::info[题目基本信息] 考察：动态规划 DP，逆元，拓扑排序，组合数学，数学（省选/NOI-）。
题目简介：
给定一棵有 $n$ 个点的数，它以 $1$ 为根，设 $f_i$ 为 $i$ 点的父亲（特别地，定义 $f_1=0$），定义拓扑序为：一个排列 $\{p_n\}$，满足：

• $\forall 1\le i<j\le n,p_j\ne f_{p_i}$

对于每个 $i\in[1,n]$，求有多少拓扑序满足 $p_i=i$（对 $998244353$ 取模）。
数据范围：

• $2\le n\le 5000$
• $\forall i\in[2,n],1\le f_i<i$

时间限制：2s。
空间限制：1G。
::::: 结论：设 $g_u$ 为只考虑 $u$ 子树内时拓扑序个数，则 $\displaystyle g_u=\frac{siz_u!}{\prod_{v\in\text{sub}u}siz_v}$，其中 $\text{sub}_u$ 表示 $u$ 子树内的结点构成的集合，$siz_u$ 表示 $u$ 的子树大小。
:::::success[证明]{open} 考虑数学归纳法。
当 $siz_u=1$ 时，$\displaystyle g_u=\frac{siz_u!}{\prod{v\in\text{sub}u}siz_v}=1$，显然成立。
当 $siz_u\ne 1$ 时，假设 $\forall v\in\text{son}_u$ 都满足条件，其中 $\text{son}_u$ 表示 $u$ 点的儿子构成的集合。
那么根据定义，我们可以得到 $g_u$ 的转移方程式为：
$$g_u=\frac{(siz_u-1)!}{\prod{v\in\text{son}u}siz_v!}\cdot\prod{v\in\text{son}u}g_v$$ 我们将 $\displaystyle g_v=\frac{siz_v!}{\prod{w\in\text{sub}v}siz_w}$ 代入推导：
$$\begin{aligned}g_u&=\frac{(siz_u-1)!}{\prod{v\in\text{son}u}siz_v!}\cdot\prod{v\in\text{son}u}g_v\&=\frac{(siz_u-1)!}{\prod{v\in\text{son}u}siz_v!}\cdot\prod{v\in\text{son}u}\frac{siz_v!}{\prod{w\in\text{sub}v}siz_w}\&=\frac{(siz_u-1)!}{\prod{v\in\text{son}u}\prod{w\in\text{sub}v}siz_w}\&=\frac{(siz_u-1)!}{\prod{v\in\complement{\text{sub}u}\{u\}}siz_v}\&=\frac{siz_u!}{\prod{v\in\text{sub}u}siz_v}\end{aligned}$$ 证毕。
::::: 证明完了上面的结论，我们直接考虑 DP，设 $f{u,i}$ 为不考虑 $u$ 子树（除 $u$ 外）内的情况下，$p_u=i$ 的方案数，显然可以得到 $f_{1,1}=1$，考虑从根到叶子进行 DFS，同时进行 DP。
考虑从 $f_{u,i}$ 转移到 $f_{v,j}$（$i<j$），这时我们需要考虑 $\complement_{\text{sub}u}\text{sub}_v\cup\{u\}$ 这部分的贡献，注意到这部分变成了一个子树，我们就可以套用上面的结论，同时也要乘上 $\displaystyle\binom{n-i-siz_v}{siz_u-siz_v-1}$ 表示在未填的位置上选出一些位置填上，我们就得到了转移方程式：
$$f{v,j}=\sum_{i=1}^{j-1}f_{u,i}\binom{n-i-siz_v}{siz_u-siz_v-1}\cdot\frac{(siz_u-siz_v-1)!}{\prod_{v\in\complement{\text{sub}u}\text{sub}_v\cup\{u\}}siz_v}$$ 但是这个转移方程式实现出来是 $\Theta(n^3)$，注意到这个转移方程式跟 $j$ 半毛钱关系都没有，我们考虑差分。
具体地，令 $j\leftarrow j-1$，我们得到：
$$f{v,j-1}=\sum_{i=1}^{j-2}f_{u,i}\binom{n-i-siz_v}{siz_u-siz_v-1}\cdot\frac{(siz_u-siz_v-1)!}{\prod_{v\in\complement{\text{sub}u}\text{sub}_v\cup\{u\}}siz_v}$$ 两式相减，得到：
$$f{v,j}-f_{v,j-1}=f_{u,j-1}\binom{n-j-siz_v+1}{siz_u-siz_v-1}\cdot\frac{(siz_u-siz_v-1)!}{\prod_{v\in\complement{\text{sub}u}\text{sub}_v\cup\{u\}}siz_v}$$ 自然得到：
$$f{v,j}=f_{v,j-1}+f_{u,j-1}\binom{n-j-siz_v+1}{siz_u-siz_v-1}\cdot\frac{(siz_u-siz_v-1)!}{\prod_{v\in\complement{\text{sub}u}\text{sub}_v\cup\{u\}}siz_v}$$ 我们设 $cnt_u=\prod{v\in\text{sub}u}siz_v$，上式就变为：
$$f{v,j}=f_{v,j-1}+f_{u,j-1}\binom{n-j-siz_v+1}{siz_u-siz_v-1}\cdot\frac{(siz_u-siz_v-1)!}{cnt_u\div siz_u\div cnt_v}$$ 这个东西预处理阶乘和逆元就可以达到可接受的复杂度了，最后的答案 $ans_u$ 就为：
$$ans_u=f_{u,u}\binom{n-u}{siz_u-1}\cdot \frac{siz_u!}{cnt_u}$$ 时间复杂度为 $\Theta(n^2)$（实现较劣会变为 $\Theta(n^2\log p)$，其中 $p$ 是模数，不知道能不能过），空间复杂度为 $\Theta(n^2)$。

code

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

:::::info[题目基本信息] 考察：动态规划 DP（$3300$）。
题目简介：
给定一个长度为 $m$ 的环，上面有编号从 $1$ 到 $m$ 的一些位置，一开始有 $n$ 个人站在 $n$ 个位置上，然后每个人会选定一个方向走 $p$ 步，求在每个位置都被至少一个人走到的基础上 $p$ 的最小值。
数据范围：

• $1\le m\le 10^9$
• $1\le n\le 10^5$
• $\forall i\in[1,n],1\le a_i\le m$

时间限制：1.5s。
空间限制：250MB。
::::: 首先注意到 $p$ 是满足单调性的，可二分答案，然后问题转化为判定 $p$ 是否合法。
放弃若干方法后，我们考虑 DP，设 $f_{i,j}$ 为考虑到第 $i$ 个人时是否能到达位置 $j$，但是每一个状态只存一个 bool 太浪费了，所以我们改设 $f_i$ 表示考虑到第 $i$ 个人时能到达的最远位置。
在推导状态转移方程前，还有一件事需要解决，那就是现在的 DP 是有后效性的，这是因为原问题是在环上做，我们考虑断环为链，但是还不能简单倍长，这样的话求出的 DP 数组就会被上一次求出的答案影响，所以我们要好好思考如何断环为链。
注意到答案下界是 $\displaystyle\max(\max_{i=1}^{n-1}a_{i+1}-a_i,a_1+m-a_n)$，如果大于等于这个值我们直接全部向一个方向走即可，我们只需要验证小于这个值的答案是否合法。
在这时，我们一定会有两个人之间不可互相走到对方的位置，我们在这里断开就不会影响答案了，我们将断开后的这条链重编号编为 $\{b_n\}$（钦定 $b_1=0$）。
这时我们就可以推状态转移方程了，我们分第 $1$ 个人（重编号后）往左或往右走分类讨论：

• 往左：这时初始条件为 $f_1=0$，最后如果 $f_n\ge m-p-1$ 则合法。
• 往右：这时第 $2$ 个人一定往左，因为 $n$ 填不满 $1$ 和 $n$ 之间的空，初始条件为 $f_2=\max(b_2,p)$，最后如果 $f_n\ge\min(m-1,m+b_2-p-1)$（实际上 $b_2$ 对应 $m-1$，$p$ 对应 $m+b_2-p-1$，但是若 $b_2$ 大，则 $m-1$ 小，所以可以在代码中简写）。

现在我们只差状态转移方程，开始分类讨论：

• 如果这一位向右走：
  此时上一位（也可能是上上位，下同）必定向右走填满了这两位中间的空隙，那么转移前提条件为 $f_{i-1}\ge b_i-1$，转移方程为 $f_i\leftarrow\max(f_i,b_i+p-1)$。
• 如果这一位向左走：
  此时上一位不一定往哪走，继续分类讨论：
  • 如果上一位向左走：
    此时上一位一定填到了这一位能填到的位置，转移前提条件为 $f_{i-1}\ge b_i-p-1$，转移为 $f_i\leftarrow\max(f_i,b_i)$。
  • 如果上一位向右走：
    此时仍需要分上一位是否填到了这一位分类讨论：
    • 如果没填到这一位：与上一位向左走转移相同。
    • 如果填到了这一位：
      虽然填到了这一位，但是不能直接转移，因为不一定与前面连续，所以我们需要从 $f_{i-2}$ 转移，前提条件为 $f_{i-2}\ge b_i-p-1$，转移为 $f_i=\max(f_i,b_{i-1}+p)$。
      同时由于有不连续转移，所以还有转移 $f_i\leftarrow\max(f_i,f_{i-1})$。

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

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-07-25 23:08:59

首黑祭。
考察：AC 自动机，树状数组，线段树，差分，常数优化。
题目简述：
小 Z 收到了一个字符串 $s$ 及一坨字符串 $\{p_n\}$，求每个 $p_i$ 在 $s$ 中出现的次数。

字符串 $t$ 在字符串 $s$ 中出现的次数定义是 $s$ 中的不同的子串 $s'$ 满足 $s'\pprox t$ 的个数。

$s$ 中的子串 $s'$ 不同指 $s'$ 在 $s$ 中出现的位置不同，即左右端点有一个不同。

$s\pprox t$ 指：

1. $|s|=|t|$
2. $\forall i,j\in[1,|s|]\cap\mathbb Z,s_i\ne t_i,s_j\ne t_j,|i-j|<k$

数据范围：

• $|s|\le 2\times 10^5$
• $\sum_{i=1}^n|p_i|\le2\times 10^5$

我们把 $s\pprox t$ 的定义翻译一下，即：

1. $|s|=|t|$
2. $\text{lcp}(s,t)+\text{lcs}(s,t)+k\ge|s|$

   这里，函数 $\text{lcp}(s,t)$ 指的是 $s$ 和 $t$ 的最长公共前缀，$\text{lcs}(s,t)$ 指的是 $s$ 和 $t$ 的最长公共后缀。

这就出现了类多模字符串匹配，掏出我们的 AC 自动机。$\forall i\in[1,n]\cap\mathbb Z$，将 $p_i$ 和 $p_i$ 的反串（包括 $s$ 和 $s$ 的反串，但为了卡常加入它们时可以不新建节点）扔进 AC 自动机里，然后算 $lst$（其实就是 $fail$，不过我不习惯用它，目的是为了避免与某些稀奇古怪的函数冲突的可能性）指针，建立 $lst$ 树。
如果 $p_i$ 与 $s$ 前缀恰好匹配到了第 $j$ 位，那么后缀至少要匹配到 $j+k+1$ 位。
注意到恰好不好计算，我们就采用差分思想。
若 $p_i$ 的第 $j$ 位在 AC 自动机上的节点是 $u$，反串 $j+k+1$ 位是 $v$，在 $s$ 上与之对应的左右端点分别是 $x,y$，那么需要满足 $x$ 在 $u$ 的子树中且 $y$ 在 $v$ 的子树中。
那么我们遍历整棵树，将询问和修改挂到树上做就可以了，具体实现见代码。

代码

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-07-30 19:08:38

不说闲话。

A. Professor GukiZ's Robot：

考察：数学。
题目简述：
在一平面直角坐标系上，小 X 要从 $(x_1,y_1)$ 移动到 $(x_2,y_2)$，每次他可以使得所在坐标的横纵坐标加上或减去 $1$ 或不改变（由于小 X 智商没有问题，所以他不能也显然不会完全不移动），求他移动的最少步数。
数据范围：

• $-10^9\le x_1,x_2,y_1,y_2\le 10^9$

我们先假设他只能上下左右移动，那么他会先向上或下移动 $|x_1-x_2|$ 步，再向左或右移动 $|y_1-y_2|$ 步。
现在他能向八个方向移动，故向左或右和向上或下的各 $\min(|x_1-x_2|,|y_1-y_2|)$ 就会合并，减少了 $\min(|x_1-x_2|,|y_1-y_2|)$ 步，所以最后答案就是 $|x_1-x_2|+|y_1-y_2|-\min(|x_1-x_2|,|y_1-y_2|)=\max(|x_1-x_2|,|y_1-y_2|)$。
时间复杂度为 $\Theta(1)$，空间复杂度为 $\Theta(1)$。

B. Grandfather Dovlet’s calculator：

考察：模拟。
题目简述：
小 I 在等红绿灯时想到了一个问题，如果他从红绿灯还剩 $b$ 秒等到了还剩 $a$ 秒，问任一秒红绿灯亮起的小灯（每个数位各有 $7$ 个小灯）根数的总和。
数据范围：

• $1\le a\le b\le 10^6$

定义 $\{a_{10}\}$ 为每个数字的亮起的小灯数，枚举 $a$ 到 $b$ 的每一秒，逐位统计亮起小灯数的总和即可。
时间复杂度为 $\Theta((b-a)\log b)$，空间复杂度为 $\Theta(1)$。

C. Pearls in a Row：

考察：贪心，STL。
题目简述：
小 K 拿到了一个数列 $\{a_n\}$，他定义合法的连续子序列 $[l,r]$ 是 $\exists l\le i<j\le r,a_i=a_j$ 的连续子序列，问该序列最多分割成多少个连续子序列并给出一种方案，无解输出 $-1$。
数据范围：

• $1\le n\le 3\times 10^5$
• $\forall i\in[1,n]\cap\mathbb Z,1\le a_i\le 10^9$

我们开一个桶判断这个数是否出现过，由于数据范围较大要开一个 map，贪心地，每次遇到重复出现的数就分割成一段，别忘了合并最后不符合条件的一段。
时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(n)$。

D. Professor GukiZ and Two Arrays：

考察：二分，STL，贪心。
题目简述：
小 A 拿到了两个数列 $\{a_n\}$ 和 $\{b_m\}$，他最多可以拿出两个数列中的各一个数交换两次，他想知道最后两数列的和的差的绝对值的最小值是多少并给出一种方案。
数据范围：

• $1\le n,m\le 2000$
• $\forall i\in[1,n]\cap\mathbb Z,j\in[1,m]\cap\mathbb Z,-10^9\le a_i,b_j\le 10^9$

我们分三种情况讨论：

1. 不进行操作，此时最小值就为 $\displaystyle|(\sum_{i=1}^na_i)-(\sum_{i=1}^mb_i)|$。
2. 进行 $1$ 次操作，此时预处理两序列的和为 $suma,sumb$，假设确定了交换的 $i$ 和 $j$ 后交换后变为了 $suma-a_i+b_j$ 以及 $sumb+a_i-b_j$，直接枚举，最小值为 $\displaystyle\min_{i=1}^n\min_{j=1}^m|suma-sumb-2a_i+2b_j|$。
3. 进行 $2$ 次操作，假设确定了交换的 $i_1,i_2,j_1,j_2$ 则最后答案为 $|suma-sumb-2(a_{i_1}+a_{i_2})+2(b_{j_1}+b_{j_2})|$，所以 $2(b_{j_1}+b_{j_2})$ 要尽量接近 $sumb-suma+2(a_{i_1}+a_{i_2})$，所以将所有的 $2(b_{j_1}+b_{j_2})$ 扔进 set 里，然后按要求模拟即可。

时间复杂度为 $\Theta((n^2+m^2)\log m^2)$，空间复杂度为 $\Theta(m^2)$。

E. New Year Tree：

考察：线段树，状态压缩。
题目简述：
小 Z 一棵树，它由 $n$ 个点组成，最初第 $i$ 个点的颜色为 $c_i$，后来有 $m$ 次操作，可以将一个子树中的颜色全部修改为一个颜色或查询一个子树内的不同颜色数。
数据范围：

• $1\le n,m\le 4\times 10^5$
• $\forall i\in[1,n]\cap\mathbb Z,1\le c_i\le 60$

注意到 $1\le c_i\le 60$，所以我们可以将 $60$ 种颜色是否出现过压缩到一个 long long 中，然后用 DFS 序将树拍到序列上，最后就是普通的区间修改区间查询了。
时间复杂度为 $\Theta(n+m\log n)$，空间复杂度为 $\Theta(n)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-07-31 21:02:30

:::info[说些闲话] 试用新科技。
:::

A. Infinite Sequence：

:::info[题目基本信息] 考察：数学。
题目简述：
小 X 拿到了一个序列 $\displaystyle\lim_{p\to+\infty}\{a_p\}$，其中：
$$a_i=\begin{cases}1&i=1\lor\exists j\in[1,i-2]\cap\mathbb Z,a_j=a_{i-1}\_{i-1}+1&\text{otherwise}\end{cases}$$ 他想求 $a_n$ 的值。
数据范围：

• $1\le n\le 10^{14}$ ::: 这个序列形为 $1,1,2,1,2,3,1,2,3,4,1,2,3,4,5\cdots$，容易发现 $i$ 第一次出现是在第 $\displaystyle\frac{(i+1)i}{2}$ 位，所以枚举在 $1$ 到 $n$ 位出现的最大的数，根据上述输出值。
  时间复杂度为 $\Theta(\sqrt n)$，空间复杂度为 $\Theta(1)$。

B. The Time：

:::info[题目基本信息] 考察：模拟。
题目简述：
小 K 看表得到了一个 $24$ 小时制的时间，他想知道 $a$ 分钟后是什么时间，由于强迫症，时间要以 hh:mm 的方式输入输出。
数据范围：

• $1\le a\le 10^4$ ::: 我们可以一分钟一分钟的往后推，先在最低位加 $1$，然后不断进位即可。
  时间复杂度为 $\Theta(a)$，空间复杂度为 $\Theta(1)$。

C. Not Equal on a Segment：

:::info[题目基本信息] 考察：STL。
题目简述：
小 I 收到了一个序列 $\{a_n\}$，他有 $m$ 次询问，第 $i$ 次询问在区间 $[l_i,r_i]$ 内是否存在一个 $p_i$ 满足 $a_{p_i}\ne x_i$，若存在给出任意一个 $p_i$，不存在输出 $-1$。
数据范围：

• $1\le n,m\le 2\times 10^5$
• $\forall i\in[1,n]\cap\mathbb Z,1\le a_i\le 10^6$
• $\forall i\in[1,m]\cap\mathbb Z,1\le l_i\le r_i\le n,1\le x_i\le 10^6$ ::: 如果在 $\forall i\in[1,m]\cap\mathbb Z,j\in[l_i,r_i]\cap\mathbb Z,a_j=x_i$，那么：
• $a_{l_i}=x_i$
• $\forall j\in(l_i.r_i]\cap\mathbb Z,a_j=a_{j-1}$

那么我们把所有的 $a_i\ne a_{i-1}$ 扔进 set 里，按照上面两个条件模拟判断即可。
时间复杂度为 $\Theta((n+m)\log n)$，空间复杂度为 $\Theta(n)$。

D. Optimal Number Permutation：

:::info[题目基本信息] 考察：构造，数学。
题目简述：
小 A 拿到了一个数 $n$，他想得到一个序列 $\{a_{2n}\}$，$\displaystyle\forall i\in[1,n]\cap\mathbb Z,\sum_{j=1}^{2n}[a_j=i]=2$，同时设 $d_i$ 为 $i$ 出现的两次的位置差距。
定义 $\displaystyle s=\sum_{i=1}^n(n-i)\times|d_i+i-n|$，在 $s$ 最小的情况下，给出一种方案。
数据范围：

• $1\le n\le 5\times 10^5$ ::: 结论题。
  结论：
• 存在方案使得 $s=0$。

:::info[证明：]
由于 $s=0$，所以 $\forall i\in[1,n]\cap\mathbb Z,(n-i)\times|d_i+i-n|=0$，下面分情况讨论：

1. $n-i=0\Leftrightarrow i=n$，没什么好说的。
2. $|d_i+i-n|=0\Leftrightarrow d_i+i=n$，注意到在序列的前一半可以放下 $d_i=n-1,n-3,\cdots\Leftrightarrow i=1,3,\cdots$ 的要求，剩余的放在后一半即可。

证毕。
::: 时间复杂度为 $\Theta(n)$，空间复杂度为 $\Theta(n)$。

E. Ants in Leaves：

:::info[题目基本信息] 考察：贪心。
题目简述：
小 L 收到了一棵有 $n$ 个节点的树，它以节点 $1$ 为根，在每个叶子结点上有一只蚂蚁，每一秒蚂蚁会向父节点爬，除非有多只蚂蚁同时往一个非根节点的节点爬，此时他们会互相谦让，小 L 可以指定哪一只蚂蚁会先往上爬，问蚂蚁都爬到根节点最少要多少秒。
数据范围：

• $2\le n\le 5\times 10^5$ ::: 注意到根节点的各个儿子节点的子树相互独立，故我们可以将所有儿子的子树的答案取最大值。
  向上爬的过程实际就是深度减 $1$ 的过程，由于深度相同的蚂蚁早晚会相遇，所以我们可以将其中一个深度加 $1$，所以我们将所有叶子的深度升序排序，然后 $dep_i\leftarrow\max(dep_i,dep_{i-1}+1)$ 即可。
  时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(n)$。

F. The Sum of the k-th Powers：

:::info[题目基本信息] 考察：拉格朗日插值。
题目简述：
小 Z 拿到了两个数 $n,k$，他想求：
$$(\sum_{i=1}^ni^k)\bmod(10^9+7)$$ 数据范围：

• $1\le n\le 10^9$
• $0\le k\le 10^6$ ::: ::::success[拉格朗日插值简介] 已知一个 $n$ 次多项式的图象过 $n+1$ 个点，第 $i$ 个点为 $(x_i,y_i)$，显然答案唯一。 :::info[答案唯一性] 列一个 $n+1$ 元一次方程组易证。
  ::: 构造的多项式为 $\displaystyle f(x)=\sum_{i=1}^{n+1}y_i\prod_{j\in[1,n+1]\cap\mathbb Z,j\ne i}\frac{x-x_j}{x_i-x_j}$，将值带入发现正确性显然。
  一般地，该式时间复杂度为 $\Theta(n^2)$。
  :::: 结论：$\displaystyle f(n)=\sum_{i=1}^ni^k$ 是一个 $k+1$ 次多项式。 :::::success[证明（默的）] 构造一个序列 $S$ 为 $\{f(1),f(2),\cdots,f(n)\}$。 定义序列 $A$ 的一阶差分序列 $\Delta A$ 为 $\{A_2-A_1,A_3-A_2,\cdots,A_{|A|}-A_{|A|-1}\}$，它的 $x$（$x\ge 2$）阶差分序列 $\Delta^xA$ 为它的 $x-1$ 阶差分序列的 $1$ 阶差分序列。 若序列 $A$ 中数字都相等，则序列 $A$ 为 $0$ 阶等差序列，若序列 $A$ 的 $x$ 阶差分序列为 $0$ 阶等差序列，则它是一个 $x$ 阶等差序列。
  结论：
• 若序列 $S$ 为 $x$ 阶等差序列，则序列的通项 $A$ 为一个 $x$ 次多项式。
• 上一条的逆命题。

::::success[证明] 设序列 $S$ 中相邻两项元素 $f(p)$ 和 $f(p-1)$ 分别可表示为 $\displaystyle\sum_{i=1}^xk_ip^i$ 和 $\displaystyle\sum_{i=1}^xk_i(p-1)^i$。
显然序列 $S$ 的一阶差分序列的次数不会高于 $x$。
由上述可得：
$$\begin{aligned}\Delta f(p-1)&=f(p)-f(p-1)\&=\sum_{i=1}^xk_ip^i-\sum_{i=1}^xk_i(p-1)^i\&=\sum_{i=1}^xk_i(p^i-(p-1)^i)\&=\sum_{i=1}^xk_i((1-1)p^i+\cdots)\end{aligned}$$ 所以它的一阶差分序列为一个 $x-1$ 次多项式，故它的通项为一个 $x$ 次多项式，所以它的 $x$ 阶差分序列为一个 $0$ 次多项式，即 $0$ 阶等差序列，故它是一个 $x$ 阶等差序列。
逆命题反推即可。
证毕。
:::: 显然，序列 $S$ 的 $1$ 阶差分序列是一个 $k$ 次多项式，即一个 $k$ 阶等差序列，所以它是一个 $k+1$ 阶等差序列，即一个 $k+1$ 次多项式。
证毕。
::::: 好的终于证完了，但是目前时间复杂度为 $\Theta(k^2)$，无法通过。
取 $k+2$ 个点，它们的横坐标为 $1$ 到 $k+2$。
那么让我们来推式子吧：
$$\begin{aligned}f(n)&=\sum_{i=1}^ni^k\&=\sum_{i=1}^{k+2}(\sum_{j=1}^ij^k)\prod_{j\in[1,k+2]\cap\mathbb Z,j\ne i}\frac{n-j}{i-j}\&=\sum_{i=1}^{k+2}(\sum_{j=1}^ij^k)\cdot\frac{(\prod_{j=1}^{i-1}n-j)\cdot(\prod_{j=i+1}^nn-j)}{(i-1)!(k+2-i)!(-1)^{k+2-i}}\end{aligned}$$ 现在式子上所有东西都能用快速幂和前缀和维护了，模数 $P=10^9+7$，按题意模拟。
时间复杂度为 $\Theta(k\log P)$，空间复杂度为 $\Theta(k)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-05 23:37:48

A. Tennis Tournament：

:::::info[题目基本信息] 考察：数学，模拟。
题目简介：
小 K 去参加了一场乒乓球比赛，有 $n$ 名选手，不断进行若干轮比赛，直至还剩 $1$ 人，下面是详细的比赛过程：
::::info[一次比赛的定义] 一次比赛有 $2$ 人，其中比赛结果不可能出现平局，$2$ 人中输的人淘汰。
:::: ::::info[一轮比赛的定义] 设有 $m$ 个人未被淘汰，令 $k$ 为最小的正整数使得 $2^k\le m$，$2^k$ 名选手进行 $2^{k-1}$ 次比赛，剩余选手直接晋级（不参加比赛）。
:::: 已知每位选手每次比赛需要 $b$ 瓶水，每次比赛的裁判需要 $1$ 瓶水，同时每位选手每场比赛需要 $p$ 块毛巾，问总共需要多少瓶水和多少块毛巾。
数据范围：

• $1\le n,b,p\le 500$ ::::: :::::info[闲话] 纯纯阅读理解题，一不小心就翻译错了。
  ::::: 按上述模拟。
  时间复杂度为 $\Theta(\log n)$，空间复杂度为 $\Theta(1)$。

B. New Skateboard：

:::::info[题目基本信息] 考察：字符串，数学。
题目简介： 小 X 获得了一个只包含数字的字符串 $s$，他想计算其中有多少个非空子串形成的数能被 $4$ 整除，子串允许有前导 $0$。
数据范围：

• $1\le |s|\le 3\times 10^5$ ::::: 根据小学知识得：一个数能被 $4$ 整除的充要条件是它的后两位拼成的数能被 $4$ 整除。
  那么我们找出所有相邻两位拼成的数能被 $4$ 整除的位置，累加答案即可。 设 $\{a_n\}$ 为字符串 $s$ 上每一位上的数字，则答案为： $$(\sum_{i=2}^n10a_{i-1}+a_i\equiv0\pmod 4)+(\sum_{i=1}^n[a_i\equiv0\pmod 4])$$ 时间复杂度为 $\Theta(n)$，空间复杂度为 $\Theta(n)$。
  ::::warning[坑点] 别忘了子串只有 $1$ 位的情况！
  ::::

C. Bear and String Distance：

:::::info[题目基本信息] 考察：贪心。
题目简介：
小 G 收到了一个长度为 $n$ 的仅由小写字母组成的字符串 $s$，定义两个字符的 $dist$ 值为两字符 ASCII 码值差，定义两个等长字符串的 $dist$ 值为两字符串每一对对应位置的 $dist$ 值之和，他想求任意一个字符串 $s'$ 满足它和 $s$ 的 $dist$ 值等于一个常数 $k$，若不存在请向他回复 $-1$。
数据范围：

• $1\le n\le 10^5$
• $0\le k\le 10^6$ ::::: 显然，若要使两字符串间 $dist$ 值最大，则对于字符串的每一位，要么改成 a，要么改成 z，看哪个和它 $dist$ 值最大，若求出来的值还小于 $k$ 则不可行，否则尽量使前面的 $dist$ 更大，构造方案即可。 时间复杂度为 $\Theta(n)$，空间复杂度为 $\Theta(n)$。

D. Magic Numbers：

:::::info[题目基本信息] 考察：数位 dp。
题目简介：
小 L 收到了 $4$ 个数 $m,d,l,r$，其中 $l,r$ 位数相同，求满足下列条件的整数 $x$ 的个数对 $10^9+7$ 取模的结果：

• $l\le x\le r$
• $x$ 从最高位到最低位数的偶数位为 $d$，奇数位不为 $d$。
• $m|x$

数据范围：

• $1\le m\le 2000$
• $0\le d\le 9$
• $1\le l\le r\le 10^{2000}$ ::::: 数位 dp。
  设 $f_{i,j,0/1,0/1}$ 为前 $i$ 位对 $m$ 取模的结果为 $j$ 且是否全都是前导 $0$ 和是否前面与 $r$ 相等。 不断记忆化搜索即可。 由于高精减不好 （懒得） 处理，所以最后要对 $l$ 判断是否符合条件。 时间复杂度为 $\Theta(|r|m)$（$|r|$ 指 $r$ 的位数），空间复杂度为 $\Theta(|r|m)$。
  ::::warning[坑点] 一开始做这题因为太久没做数位 dp 导致：

1. 忘记根据是否有前导零（这题不用）和前面几位是否与 $r$ 相同。
2. 将 $l,r$ 拆开（这题也不用）。
3. 将 $l,r$ 拆开后每次都进行清空 $dp$ 数组。
   ::::

E. Zbazi in Zeydabad：

:::::info[题目基本信息] 考察：树状数组。
题目简介：
小 A 拿到了一个 $n\times m$ 的由 z 和 . 组成的网格图 $s$，令其中为 z 的位置 $(i,j)$ 上 $a_{i,j}=1$，否则 $a_{i,j}=0$。
他想知道满足下列条件的有序正整数四元组 $(lx,ly,rx,ry)$ 的数量：

• $1\le lx\le rx\le n,1\le ly\le ry\le m$
• $rx-lx=ry-ly$
• $\forall i\in[ly,ry]\cap\mathbb Z,a_{lx,i}=a_{rx,i}=1$
• $\forall i\in[lx,rx],a_{i,lx+ry-i}=1$ 数据范围：
• $1\le n,m\le 3000$ ::::: 想要固定该 Z 字形的一个点位置，但是固定那个呢？
• 若固定左上点或右下点，则 Z 字形的两条边还会动。
• 若固定左下点或右上点，则 Z 字形只有一条边会动，显然更优。

故我们固定右上点，想要快速统计贡献，所以我们维护以 $(i,j)$ 点为右端点的极长 z 序列长度 $a_{i,j}$ 以及以 $(i,j)$ 点为右上端点的极长 z 序列长度 $b_{i,j}$，则右下点的横坐标（这里的横坐标与平面直角坐标系的横坐标相反）$rx$ 就必须满足 $i\le rx\le i+\min(a_{i,j},b_{i,j})-1$。
但并非每一个都满足要求，还要满足 $j-a_{rx,j}+1\le j-(rx-i)$。
对上式根据参变分离法移项并合并同类项得 $rx-a_{rx,j}+1\le i$，这时就很显然了，对于每一列建立树状数组维护即可。
时间复杂度为 $\Theta(nm\log n)$，空间复杂度为 $\Theta(nm)$。
:::::warning[坑点] 本题卡空间，需要关闭 long long，仅对最后答案开 long long。
:::::

F. Bear and Fair Set：

:::::info[题目基本信息] 考察：最大流。
题目简介：
小 Z 收到了一些限制条件，他想知道是否存在一个集合 $S$ 满足下面这些条件：

• $\forall x\in S,x\in[1,b]\cap\mathbb Z$
• $|S|=n$
• $\displaystyle\forall i\in\{0,1,2,3,4\},\sum_{x\in S}[x\equiv i\pmod 5]=\frac{n}{5}$
• $\displaystyle\forall i\in[1,q],\sum_{x\in S}[x\in[1,u_i]]=t_i$

数据范围：

• $5\le n\le b\le 10^4,5|n$
• $1\le q\le 10^4$
• $\forall i\in[1,q]\cap\mathbb Z,1\le u_i\le b,0\le t_i\le n$ ::::: 考虑如何建图。
  首先我们令 $u_0=t_0=0$ 且 $u_{q+1}=b,t_{q+1}=n$，同时令 $q\leftarrow q+1$，对序列 $\{u_q\}$ 和 $\{t_q\}$ 进行差分，同时判掉一部分不合法。
  我们此时从源点向第 $i$ 个约束条件连 $t_i$ 流量，同时从约束条件分别向 $5$ 个虚点连对 $5$ 取模余一定值的数量，最后将这 $5$ 个虚点分别向汇点连 $\displaystyle\frac{n}{5}$ 的流量，跑最大流即可。 :::::warning[坑点] 由于 C++ 的除法向 $0$ 取整，所以除之前要先加 $5$。
  ::::: 时间复杂度为 $\Theta(n\sqrt n)$，空间复杂度为 $\Theta(q)$。 :::::success[对时间复杂度的一点说明] oi-wiki 下对于单位流情况下的复杂度的解释
  考虑将大于 $1$ 的边权拆成多个 $1$ 的边权，就会发现只有 $\Theta(n)$ 条边，故总时间复杂度为 $\Theta(n\sqrt n)$。
  :::::

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

:::::warning[约定] 除特殊规定外，本文章下所有数均限定在整数域。
:::::

A. Grandma Laura and Apples：

:::::info[题目基本信息] 考察：数学。
题目简介：
小 B 在卖苹果，每个苹果 $p$ 元钱，现在她卖完了苹果，但是她年纪大了记性不好，忘了最开始有几个苹果，只知道有 $n$ 位顾客，每位顾客买走了当时所剩苹果的一半，如果当时苹果数为奇数那么她就会慈祥地送他们半个苹果（不花钱，同时她很清楚地记得有没有送每位顾客半个苹果）。
然后现在小 B 想要知道她应得多少钱，以便看看有没有顾客耍她。
数据范围：

• $1\le n\le 40$
• $2\le p\le 100,2|p$ ::::: 注意到 $2|p$，且根据题目，小 B 只可能卖出（送出除外）几个或者几个半苹果，所以最后结果能用整型变量储存。
  然后倒着推，边求出当时还有几个苹果，边求出后面一共得了多少钱，按题意模拟即可。
  时间复杂度为 $\Theta(n)$，空间复杂度为 $\Theta(n)$。

B. Alice, Bob, Two Teams：

:::::info[题目基本信息] 考察：前缀和。
题目简介：
小 X 和小 K 在玩一个游戏。
场上有 $n$ 名战士站成一排，第 $i$ 名战士的战力为 $p_i$。
最开始小 X 先将 $n$ 名战士分成两队（A 队和 B 队），然后小 K 将这一排的一个前缀或后缀的战士进行操作，使得 A 队的去 B 队，B 队的去 A 队，A 队归小 X，B 队归小 K。
现在小 X 分好了队，小 K 想要使自己战队总战力尽量大，问最大值是多少。
数据范围：

• $1\le n\le 5\times 10^5$
• $\forall i\in[1,n],1\le p_i\le 10^9$ ::::: 提到前缀和后缀，我们便想到前缀和和后缀和，维护它们，然后枚举前缀和后缀的端点，依题意翻转前后缀，用前后缀和维护即可。 时间复杂度为 $\Theta(n)$，空间复杂度为 $\Theta(n)$。

C. The Smallest String Concatenation：

:::::info[题目基本信息] 考察：排序，数学。
题目简介：
小 I 收到了 $n$ 个字符串 $\{s_n\}$，他想知道若把这些字符串按一定顺序拼成一个字符串，使这个字符串字典序最小，求这个字符串。
数据范围：

• $1\le n\le 5\times 10^4$
• $\forall i\in[1,n],1\le|s_i|\le 50$
• $\displaystyle\sum_{i=1}^n|s_i|\le5\times 10^4$ ::::: :::::info[闲话] 你说的对，这个题很简单，但是我忘了邻项交换法。
  ::::: 运用邻项交换法，若两个字符串 $a$ 和 $b$ 进行比较，则若 $a+b<b+a$（$+$ 在这里表示字符串拼接），则 $a$ 应在前面。 根据这个方式排序即可。 时间复杂度为 $\displaystyle\Theta(\sum|s|\log n)$（在这里 $\displaystyle\sum|s|=\sum_{i=1}^n|s_i|$，下同），空间复杂度为 $\displaystyle\Theta(\sum|s|)$。

D. Longest Subsequence：

:::::info[题目基本信息] 考察：桶，数学。
题目简介：
小 A 收到了一个数列 $\{a_n\}$ 和一个数字 $m$。他想知道这个数列的子序列的最小公倍数不大于 $m$ 的条件下，子序列最长是多少，并给出这个子序列和它的最小公倍数。

• 定义空序列的最小公倍数为 $1$。

数据范围：

• $1\le n,m\le 10^6$
• $\forall i\in[1,n],1\le a_i\le 10^9$ ::::: 注意到 $m\le 10^6$，所以我们可以给 $\{a_n\}$ 中的数开桶，然后统计通过调和级数统计能整除每个数的 $\{a_n\}$ 中的数的个数，然后统计答案即可。 :::::info[闲话] 写的时候一时忘了调和级数叫什么在 HL 群中问了下。
  ::::: 时间复杂度为 $\Theta(m\log m)$，空间复杂度为 $\Theta(n+m)$。 :::::warning[坑点] 注意到求的是最小公倍数，因此统计答案时应该取最小的满足条件的数。
  同时我们要把初始最小值设成负数，以免出现空序列的情况。
  同时注意到 $a_i\le 10^9$，所以需要特判 $a_i>m$。
  :::::

E. Thief in a Shop：

:::::warning[咕咕咕] FFT 不会，咕了。
:::::

F. Magic Matrix：

:::::info[题目基本信息] 考察：最小生成树。
题目简介：
小 Z 收到一个 $n\times n$ 的矩阵 $a$，他想知道这个矩阵 $a$ 符不符合以下条件：

• $\forall i\in[1,n],a_{i,i}=0$
• $\forall i,j\in[1,n],a_{i,j}=a_{j,i}$
• $\forall i,j,k\in[1,n],a_{i,j}\le\max(a_{i,k},a_{k,j})$

数据范围：

• $1\le n\le 2500$
• $\forall i,j\in[1,n],0\le a_{i,j}\le 10^9$ ::::: 三个条件中的前两个非常好维护，第三个条件需要优化。
  考虑建图（通过观察标签易得），在 $i$ 和 $j$ 之间连边权为 $a_{i,j}$ 的边，然后注意到 $a_{i,j}\le\max(a_{i,k},a_{k,j})$，其实就指 $i$ 和 $j$ 之间不通过边权小于 $a_{i,j}$ 联通。
  所以我们考虑到应用 Kruskal 进行求解，枚举每一坨 $a_{i,j}$ 相等的边，这一坨一起判断，一起加边即可。 时间复杂度为 $\Theta(n^2\log n^2)$，空间复杂度为 $\Theta(n^2)$。 :::::warning[坑点] 注意到 $n\times n$ 有 $6.25\times 10^7$，相当于每秒至少要读 $1.25\times 10^7$ 个数，因此不要使用 scanf。
  :::::

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

:::::warning[注释] 除特殊标记外，本文中变量均为整数。
::::: :::::info[闲话] 可能是暑假最后一篇了。
:::::

A. Gabriel and Caterpillar：

:::::info[题目基本信息] 考察：数学，模拟（$800$）。
题目简述：
小 K 发现了一只毛毛虫，它在第 $0$ 天 $14$ 点位于高度 $h_1m$，它在每天 $10\sim22$ 点向上以 $am/h$ 的速度爬，其余时间在向下以 $bm/h$ 的速度掉，问第几天的 $14$ 点他的高度会到达 $h_2m$（高度可以为负），不可能给出 $-1$？
数据范围：

• $1\le h_1,h_2,a,b\le 10^5$ ::::: 容易发现，若一天内还没有爬上去，且最后位置回到了 $h_1$ 甚至更低，则一定爬不上去。 否则由于数据范围较小，直接模拟即可。 时间复杂度为 $\Theta(V)$，空间复杂度为 $\Theta(1)$。

B. z-sort：

:::::info[题目基本信息] 考察：数学，构造（$1000$）。
题目简述：
小 X 收到了一个序列 $\{a_n\}$，现在将其排序，使得（$1\le i\le n$）：

• 若 $2\mid i$，则 $a_i\ge a_{i-1}$。
• 若 $2\nmid i$，则 $a_i\le a_{i-1}$。

构造一组合法解，若无解输出 Impossible。
数据范围：

• $1\le n\le 1000$
• $\forall i\in[1,n],1\le a_i\le 10^9$ ::::: 容易发现若 $\forall i,j\in[1,n],2\mid i,2\nmid j,a_i\ge a_j$，则这种序列是满足要求的，直接按照这样排序模拟即可。 时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(n)$。

C. Foe Pairs：

:::::info[题目基本信息] 考察：STL，双指针（$1800$）。
题目简述：
小 I 收到了一个长度为 $n$ 的排列 $\{p_n\}$，现在给出 $m$ 组限制，第 $i$ 组限制为 $a_i,b_i$，问有多少组区间 $[l,r]$ 满足：

• $1\le l\le r\le n$
• $\forall i\in[1,m],j\in[l,r],a_i\ne p_j\lor\forall j\in[l,r],b_i\ne p_j$

数据范围：

• $1\le n,m\le 3\times 10^5$
• $\forall i\in[1,n],1\le p_i\le n$
• $\forall i\in[1,m],1\le a_i,b_i\le n$ ::::: 首先我们要找到 $a_i,b_i$ 的具体位置，所以我们要开桶（较小的设为 $idxa$，较大的设为 $idxb$），然后找到若 $l\le idxa\le r$，则 $r$ 最少到哪里。
  首先一个点的可以直接预处理，多个点的话先放一边。
  然后我们想到若左端点右移，则右端点的取值范围也会右移，所以我们想到双指针。
  我们回到多个点的右端点的取值范围其实就是取最小值，同时也要支持增加或减少，所以我们想到 multiset，最后直接模拟即可。
  时间复杂度为 $\Theta(n\log n+m)$，空间复杂度为 $\Theta(n)$。

D. Nested Segments：

:::::info[题目基本信息] 考察：树状数组，线段树（$1800$）。
题目简述：
小 A 收到了 $n$ 条线段，它们都在同一条数轴上，问每条线段各包含几条其他的线段（保证没有线段完全重合）。
::::info[包含的定义] 若对于所有的在线段 $a$ 上的点都在线段 $b$ 上，则称线段 $b$ 包含线段 $a$。
:::: ::::info[完全重合的定义] 若线段 $a$ 包含线段 $b$ 且线段 $b$ 包含线段 $a$，则称线段 $a$ 和线段 $b$ 完全重合。
:::: 数据范围：

• $1\le n\le 2\times 10^5$ ::::: 容易发现若线段 $a$ 的两端为 $l_a$ 和 $r_a$，线段 $b$ 的两端为 $l_b$ 和 $r_b$，线段 $a$ 包含线段 $b$，则 $l_a\le l_b\le r_b\le r_a$。
  容易发现这就是一个二维偏序问题，将线段端点离散化后按左端点降序排序，用树状数组或线段树统计答案即可。
  时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(n)$。

E. Pursuit For Artifacts：

:::::info[题目基本信息] 考察：边双连通分量，dfs（$2300$）。
题目简述：
小 L 收到一张 $n$ 个点 $m$ 条边的简单无向连通图，边边权为 $0$ 或 $1$。
小 L 要在这张图中游走，每条边只能通过一次（两个方向加起来一次），问是否存在一条 $a$ 到 $b$ 的边，满足路径中至少有一条边边权为 $1$。
数据范围：

• $1\le n\le 3\times 10^5$
• $0\le m\le 3\times 10^5$
• $1\le a,b\le n$ ::::: :::::info[闲话] 发现自己的边双连通分量是假的。
  ::::: 容易发现若一个环（一个双联通分量）中存在一个边权为 $1$ 的边，那么经过这个双联通分量的路径一定有方法使路径满足条件。
  上面的性质启示我们用 tarjan 缩点，缩完点后直接 dfs 判断即可。 时间复杂度为 $\Theta(n+m)$，空间复杂度为 $\Theta(n+m)$。

F. Ants on a Circle：

:::::info[题目基本信息] 考察：数学（$2800$）。
题目简述：
小 Z 发现了一个环，长度为 $m$，位置编号为 $1$ 到 $m$，在这个环上有 $n$ 只蚂蚁，它们分别位于不同位置且面向不同方向。
小 Z 在那里看了 $t$ 秒，每只蚂蚁都会以 $1m/s$ 的速度向自己面向的方向前进，中途遇到其他蚂蚁会调头，由于他忙人多忘事，他忘了最后他们的位置，但是他记得初始状态，他想让你给出终止状态。
数据范围：

• $2\le n\le3\times 10^5$
• $2\le m\le 10^9$
• $0\le t\le 10^{18}$ ::::: 我们按照常规套路，先假设这些蚂蚁碰头后会互相穿过去，这样我们就可以求出所有蚂蚁的位置，但无法知道谁是谁的。
  这时候我们注意到由于掉头，所以每只蚂蚁的相对位置一定不会改变，也就是说我们得到一个性质：一只蚂蚁一定一直在另外两只蚂蚁中间。
  那么我们把每秒从位置编号较小的蚂蚁开始编号，那么编号改变只可能有以下情况：

1. 两只蚂蚁相遇： 这种情况其实根据上面那条性质就可以搞定了，问题在于下面这一种。

2. 一只蚂蚁从 $m$ 到 $1$ 或者从 $1$ 到 $m$：
   这种情况由于情况 $1$ 已经解决就比较简单了，每只蚂蚁经过 $m$ 到 $1$ 或 $1$ 到 $m$ 的次数能 $\Theta(1)$ 求出，那么对于不同蚂蚁而言（这里以从 $m$ 到 $1$ 为例，$1$ 到 $m$ 同理）：

   • 对于自己，自己的相对位置编号会减去 $n-1$。
   • 对于其它蚂蚁，它们的相对位置编号会加上 $1$。

   那么注意到这两种操作在模 $n$ 意义下是等价的，所以统一处理即可。

所以，将原位置和终止位置排序，记录答案，统一输出即可。
时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(m)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-29 13:31:02

:::::info[闲话] 收回我在 EDU10 题解里的闲话。
:::::

A. Co-prime Array：

考察：数学（$1200$）。
题目简介：
给你一个序列 $\{a_n\}$，求插入一定数字使其满足下列条件的最小插入数量，并构造一种方案。

• $\forall i\in[1,|a|),\gcd(a_i,a_{i+1})=1$

数据范围：

• $1\le n\le 1000$
• $\forall i\in[1,n],1\le a_i\le 10^9$

注意到对于任何正整数 $x$，满足 $\gcd(x,1)=1$，所以我们加入 $1$ 一定不劣。
那么我们对于所有不符合条件的相邻数对，在它们之间插入一个 $1$ 即可。
时空复杂度均为 $\Theta(n)$。

B. Seating On Bus：

考察：模拟（$1000$）。
题目简介：
有一个有 $n$ 排 $4$ 列座位的公交车，有 $m$ 位乘客要上车，按照从靠窗到不靠窗（第一关键字），从前到后（第二关键字），从左两排到右两排（第三关键字）的顺序坐，下车时按从前到后（第一关键字），从左两排到右两排（第二关键字），从不靠窗到靠窗（第三关键字），求每一位下车的乘客是第几个上车的。
数据范围：

• $1\le n\le 100$
• $1\le m\le 4n$

模拟即可，懒得讲。
时空复杂度均为 $\Theta(n)$。

C. Hard Process：

考察：前缀和，双指针（$1600$）。
题目简介：
给你只含 $0$ 和 $1$ 的序列 $\{a_n\}$ 和整数 $k$，求满足下列条件的 $l,r$ 中可能的最大的 $r-l+1$ 并构造一种符合条件的操作后的序列。

• $1\le l\le r\le n$
• 能通过最多 $k$ 次操作使得 $\forall i\in[l,r],a_l=1$
  • 操作：选择一个 $pos\in[1,n],a_{pos}\leftarrow 1$

数据范围：

• $1\le n\le 3\times 10^5$
• $0\le k\le n$

操作等价于选择一个 $pos\in[1,n],a_{pos}=0,a_{pos}\leftarrow 1$，因为这样操作才有效。
那么条件就等价于 $\displaystyle\sum_{i=l}^r[a_i=0]\le k$，这个东西显然可以运用前缀和维护。
然后我们注意到最大的合法的 $r$ 是一定随 $l$ 的增大而不降的，所以我们可以双指针维护。
时空复杂度均为 $\Theta(n)$。

D. Number of Parallelograms：

考察：计算几何（$1900$）。
题目简介：
给定平面上的 $n$ 个点，求从中选取四个点使得这四个点构成平行四边形的方案数。
数据范围：

• $1\le n\le 2000$

我们先证明四边形 $ABCD$ 为平行四边形的一个充要条件为 $|x_A-x_C|=|x_B-x_D|$ 且 $|y_A-y_C|=|y_b-y_D|$。
:::::success[必要条件] 如图：

初中数学，$ASA$ 证明全等。
::::: :::::success[充分条件] 同上。
$SAS$ 证明全等。
::::: 那么根据证明，我们对每条线开一个 pair，然后排序统计即可。
时间复杂度为 $\Theta(n^2\log n)$，空间复杂度为 $\Theta(n^2)$。

E. Different Subsets For All Tuples：

考察：组合数学（$2300$）。
题目简述：
存在一个序列 $\{a_n\}$，且 $\forall i\in[1,n],a_i\in[1,m]$，求所有可能序列的不同子序列（包括空序列）个数之和，并对 $10^9+7$ 取模。
数据范围：

• $1\le n,m\le 10^6$

注意到本题需要对不同的子序列计数，所以我们只对第一次出现的子序列计数。也就是说，对于子序列的下标 $\{b_k\}$（钦定 $b_0=0$），$\forall i\in[1,k],j\in[b_{i-1}+1,b_i-1],a_j\ne a_{b_i}$。
那么我们就推出了最后答案的表达式：
$$(\sum_{i=1}^nm^i\sum_{j=i}^n\binom{j-1}{i-1}m^{n-j}(m-1)^{j-i})+m^n$$ （加 $m^n$ 是因为空序列是任何一个序列的子序列，$i$ 枚举的是子序列长度，$j$ 枚举的是子序列下标 $\{b_i\}$ 中 $b_i$ 的值，即子序列终止位置）
注意到计算这个式子时间复杂度至少为 $\Theta(n^2)$，所以我们要对这个式子的前面一大坨进行化简。
$$\begin{aligned}\sum_{i=1}^nm^i\sum_{j=i}^n\binom{j-1}{i-1}m^{n-j}(m-1)^{j-i}&=\sum_{i=1}^n\sum_{j=i}^n\binom{j-1}{i-1}m^{n-j+i}(m-1)^{j-i}\&=\sum_{j=1}^n\sum_{i=1}^j\binom{j-1}{i-1}m^{n-j+i}(m-1)^{j-i}\&=\sum_{j=1}^nm^{n-j+1}\sum_{i=1}^j\binom{j-1}{i-1}m^{i-1}(m-1)^{j-i}\end{aligned}$$ 注意到这玩意特像二项式定理，直接令 $i_1=i-1$。
$$\begin{aligned}\sum_{j=1}^nm^{n-j+1}\sum_{i=1}^j\binom{j-1}{i-1}m^{i-1}(m-1)^{j-i}&=\sum_{j=1}^nm^{n-j+1}\sum_{i_1=0}^{j-1}\binom{j-1}{i_1}m^{i_1}(m-1)^{j-i_1-1}\&=\sum_{j=1}^nm^{n-j+1}(2m-1)^{j-1}\end{aligned}$$
这个式子直接预处理 $m$ 和 $2m-1$ 的幂次即可线性计算，最后别忘了加上 $m^n$。
时空复杂度均为 $\Theta(n)$。

F. Bear and Bowling 4：

考察：斜率优化 dp（$2500$）。
题目简介：
给你序列 $\{a_n\}$，求：
$$\max_{l=1}^n\max_{r=l}^n\sum_{i=l}^r(i-l+1)a_i$$ 数据范围：

• $1\le n\le 2\times 10^5$
• $\forall i\in[1,n],|a_i|\le 10^7$

我们先考虑如何快速求 $\displaystyle\sum_{i=l}^r(i-l+1)a_i$，我们对其变形：
$$\begin{aligned}\sum_{i=l}^r(i-l+1)a_i&=\sum_{i=l}^ria_i-(l-1)a_i\&=\sum_{i=l}^ria_i-(l-1)\sum_{i=l}^ra_i\end{aligned}$$ 那么我们维护前缀和（下文中 $num$ 指 $ia_i$ 的前缀和，$sum$ 指 $a_i$ 的前缀和）即可快速求得。
注意到现在时间复杂度仍是 $\Theta(n^2)$，考虑继续优化。
考虑枚举 $r$，求 $l$。
设 $f_i$ 为以 $i$ 结尾的连续子序列的最大权值，那么就有：
$$\begin{aligned}f_i&=\max_{j=1}^i(num_i-num_{j-1}-(j-1)(sum_i-sum_{j-1}))\&=\max_{j=1}^i((j-1)sum_{j-1}-num_{j-1})+num_i-(j-1)sum_i\end{aligned}$$ 我们假设已经找到了最大值对应的 $j$，那么就有：
$$f_i=(j-1)sum_{j-1}-num_{j-1}+num_i-(j-1)sum_i$$ 移项：
$$f_i-num_i=-sum_i(j-1)+(j-1)sum_{j-1}-num_{j-1}$$ 这是一个斜率优化的形式，不妨令 $y=f_i-num_i,k=-sum_i,x=j-1,b=(j-1)sum_{j-1}-num_{j-1}$。
注意到这道题 $x$ 单调递增，而 $k$ 并不，所以我们要通过在单调队列里二分来维护一个凸包。
然后我们注意到这个题没必要定义 $f_i$……
时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(n)$。

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

A. Buses Between Cities：

:::::info[题目基本信息] 考察：数学（$\color{yellow}1600$）。
题目简介：
有两座名为 A 市和 B 市的城市，它们之间有公交车行驶，公交车每天都从 A 或从 B 发车，始发车时间为 $05:00$，末发车时间不晚于 $23:59$，A 市发车间隔为 $a$ 分钟，行驶时间为 $t_a$ 分钟，B 市则分别为 $b$ 分钟和 $t_b$ 分钟。
你驾驶着一辆从 A 市一时刻发出的公交车，求你在 A 市和 B 市之间的道路上（不含 A 市和 B 市）遇到了几辆公交车。
数据范围：

• $1\le a,t_a,b,t_b\le 120$ ::::: 不妨用从 B 市的始发时间代表每一辆公交车，发现我们没必要弄清楚是在公交车是在哪里相遇的，我们只需要弄清楚相遇几次。 也就是说，我们只需要弄清楚这段时间遇到的公交车的始发时间区间即可，后面几辆公交车就好求了。
  时空复杂度均为 $\Theta(1)$。

B. Shopping：

:::::info[题目基本信息] 考察：模拟（$\color{orange}1400$）。
题目简述：
你是一个卖家，售卖 $k$ 种物品，编号从 $1$ 到 $k$，初始排列为 $\{p_k\}$，有 $n$ 个买家来你这买东西，每人买了 $m$ 个编号不同的物品，每次购买后你都要一次进行如下操作：

1. 记 $pos$ 为该物品在 $\{p_k\}$ 中出现的位置。
2. 花费 $pos$ 的体力将该物品挪到第一位。

问最后花费的体力。
数据范围：

• $1\le m\le k\le 100$
• $1\le n\le 100$ ::::: 模拟即可。
  时间复杂度为 $\Theta(nmk)$，空间复杂度为 $\Theta(nm+k)$。

C. Simple Strings：

:::::info[题目基本信息] 考察：贪心（$\color{orange}1300$）。
题目简介：
给你一个仅包含英文小写字母的字符串 $s$，每次操作可以将字符串里的一个字符修改成另一个英文小写字母，问经过最少操作后的一种使得相邻字符不同的一种方案。
数据范围：

• $1\le |s|\le 2\times 10^5$ ::::: 我们可以直接贪心，如果一个字符与它的前一个字符相同我们就直接修改成另一个与前后字符均不相同的字符。
  证明显然。 时空复杂度均为 $\Theta(n)$。

D. Simple Subset：

:::::info[题目基本信息] 考察：数学，质数筛（$\color{green}1800$）。
题目简介：
有一个可重集 $A$，满足 $|A|=n$，求它的最大子集满足：元素两两的和均是质数。
数据范围：

• $1\le n\le 1000$
• $\forall i\in[1,n],1\le a_i\le 10^6$ ::::: 注意到除了 $2$ 外偶数都不是质数，也就是说除了最终集合内的元素两两除了两个 $1$ 外奇偶性均不同，也就是说，最多只能有 $2$ 个数大于 $1$，$1$ 同时若能选则尽量全选。那么我们根据以下情况讨论：

1. 无 $1$ 且无大于 $1$ 的数。
2. 无 $1$ 且有一个大于 $1$ 的数。
3. 无 $1$ 且有两个大于 $1$ 的数。
4. 有所有 $1$ 且无大于 $1$ 的数。
5. 有所有 $1$ 且有一个大于 $1$ 的数。
6. 有所有 $1$ 且有两个大于 $1$ 的数。

我们来简化一下分类讨论：

• 以下情况可能会较优，同时它们的合法条件分别是：
  1. 无 $1$ 且有一个大于 $1$ 的数。
     条件任意。
  2. 无 $1$ 且有两个大于 $1$ 的数（设为 $x,y$）。
     条件为 $x+y\in\text{prime}$。
  3. 有 $1$ 且无大于 $1$ 的数。
     条件任意。
  4. 有 $1$ 且有一个大于 $1$ 的数（设为 $x$）。
     条件为 $x+1\in\text{prime}$。
• 以下情况不优或不合法：
  1. 无 $1$ 且无大于 $1$ 的数。
     由于根据上述，答案至少为 $1$，所以该情况不优。
  2. 有 $1$ 且有两个大于 $1$ 的数（设为 $x,y$）。
     考虑反证法：
     $\because x+1,y+1,x+y\in\text{prime},x>1,y>1$
     $\therefore x+1>2,y+1>2,x+y>2$
     $\therefore x+1,y+1,x+y\in\{2k+1|k\in\mathbb Z\}$
     $\therefore x+y\in\{2k,k\in\mathbb Z\}$
     推出矛盾。

根据上述模拟。
时间复杂度为 $\Theta(n^2)$，空间复杂度为 $\Theta(n)$。

E. Beautiful Subarrays：

:::::info[题目基本信息] 考察：trie（$\color{green}2100$）。
题目简介：
给你序列 $\{a_n\}$，求满足下列条件的 $(l,r)$ 的个数：

• $1\le l,r\le n$
• $\displaystyle\bigoplus_{i=l}^ra_i\ge k$

数据范围：

• $1\le n\le 10^6$
• $1\le k\le 10^9$
• $\forall i\in[1,n],1\le a_i\le 10^9$ ::::: 显然，我们可以维护一个异或前缀和记作 $\{sum_n\}$，那么原条件可以转化为 $sum_r\oplus sum_{l-1}\ge k$，这个显然可以用 trie 树维护。
  时空复杂度均为 $\Theta(n\log V)$。

F 不会/ll