本文章由 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)$。