CF622(EDU7) 题解 / 拉格朗日插值学习笔记

· · 题解

:::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 的值。
数据范围：

那么我们把所有的 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 最小的情况下，给出一种方案。
数据范围：

:::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 可以指定哪一只蚂蚁会先往上爬，问蚂蚁都爬到根节点最少要多少秒。
数据范围：

::::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)。