CF622(EDU7) 题解 / 拉格朗日插值学习笔记
zrl123456
·
·
题解
:::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}\\a_{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，下面分情况讨论：
-
-
| 证毕。 |
| 时间复杂度为 \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-A2,\cdots,A{ |
| 若序列 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)。