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

A

每个序列的长度递增的，容易证明只需要 $O(\sqrt n)$ 个序列，总长度就能超过 $n$。

B

scanf("%d:%d") 可以较为快捷的读入。

C

求给定子数组中哪个位置上的数不等于给定的数 $x$。

考虑预处理每种数字在哪些区间没有出现过，并以端点升序记录。

查询的时候，如果存在一个合法的区间，那么右端点大于等于 $l$ 的最小的区间一定是合法的。

D

长度为 $2n$ 的数列，包含 $[1,n]$ 的数，每个数出现了两次，令 $d_i$ 为 $i$ 的两次出现位置的差。

求如何排列这个序列，使得 $\sum\limits_{i=1}^n (n-i)|d_i+i-n|$ 最小。

注意到原式的每一项都大于等于 $0$，总和也大于等于 $0$。

猜想存在一种构造方案使得这个值是 $0$。

这就要求每一项都构造出 $0$。

由此可得 $d_1=n-1,d_2=n-2,d_3=n-3,\cdots,d_{n-1}=1$，$d_n$ 可以等于任何值。

首先将两个 $1$ 放到 $1,n$ 的位置，两个 $3$ 放到 $2,n-1$ 的位置，依次类推。

然后把两个 $2$ 放到 $n+1,2n-1$ 的位置，两个 $4$ 放到 $n+2,2n-2$ 的位置，依次类推。

最后如果剩下两个位置，那就用来放 $n$。

E

给定一棵树，每个叶子节点有一只蚂蚁。

每秒可以同时移动一些蚂蚁，但要求除了 $1$ 以外任何节点不能有超过两只蚂蚁，求最少多少秒将所有蚂蚁移动到 $1$。

注意到 $1$ 的每个子树都是独立的，可以对于每个子树单独算答案，最后取 max。

考虑单个子树内部，让深度最浅的蚂蚁先去。

随后，深度第 $2$ 浅的蚂蚁至少在前一只蚂蚁的下一秒才能到达终点，这个时间与自己原本与 $1$ 的距离取 max 就是真实时间。

后面依次类推就可以。

本题思路在于先将整个问题拆分为多个同类的子任务。

对于单个子任务，考虑实际顺序是怎么样的，根据这个过程去逐步递推求解。

F

给定 $n,k$，求 $\sum\limits_{i=1}^{n} i^k \pmod {{10}^9+7}$，$n \le 10^9,k \le 10^6$。

本题的答案是一个 $k+1$ 次多项式，但是我不会证明，这个坑以后再填。

拉格朗日插值的复杂度是 $O(k^2)$ 的，但是可以带入一些特殊值优化计算过程，此处代入 $1,2,\cdots,k+2$。

回想一下拉格朗日插值的形式，给定 $n$ 组 $x_i,y_i$，代表 $f(x_i)=y_i$。

然后 $f(p) = \sum\limits_{i=1}^n \frac{\prod\limits_{j \in [1,n],j\neq i}(p-x_j)}{\prod\limits_{j \in [1,n],j\neq i}(x_i-x_j)} y_i$。

回到本题，式子变为：
$f(p) = \sum\limits_{i=1}^{k+2} \frac{\prod\limits_{j \in [1,k+2],j\neq i}(p-j)}{\prod\limits_{j \in [1,k+2],j\neq i}(i-j)}\sum\limits_{j=1}^{i} j^k$。

考虑对于 $\forall x \in [1,k]$，右边式子里面 $i=x$ 时的贡献 $g_x$。

$g_x = \frac{\prod\limits_{j \in [1,k+2],j\neq x}(p-j)}{\prod\limits_{j \in [1,k+2],j\neq x}(x-j)}\sum\limits_{j=1}^{x} j^k$。

$\sum\limits_{j=1}^x j^k$ 可以预处理，$O(1)$ 计算。

$\prod\limits_{j \in [1,k+2],j\neq x}(p-j)$ 相当于 $\prod\limits_{j \in [1,k+2]}(p-j)$ 乘上 $p-x$ 的逆元，同样可以通过预处理逆元 $O(1)$ 计算。

$\prod\limits_{j \in [1,k+2],j\neq x}(x-j) = \prod\limits_{j=1}^{x-1}(x-j)\prod\limits_{j=x+1}^{k+2} (x-j) = \prod\limits_{j=1}^{x-1} j \prod\limits_{j=1}^{k+2-x} (-j)$。
本部分可以预处理阶乘，逆元乘积 $O(1)$ 计算。

我们成功得到了一个 $O(k)$ 的算法！