CF622F The Sum of the k-th Powers题解

### 写在前面的话 由于本菜鸡数学水平过差，在写这题的时候不懂为什么 $ \sum\limits_{i=1}^N {i^k}$ 是 $\text{k+1} $ 次多项式，在做完之后希望可以帮助到像我一样数学不好的同学，所以本文主要证明$ \sum\limits_{i=1}^N {i^k}$ 是 $\text{k+1} $ 次多项式 ~~知道的大佬们直接跳过好了~~ --- ### 简单证明 参考资料：《数学奥林匹克竞赛小丛书（第二版） 高中卷6 -- 数列与数学归纳法》 首先看一个最基本的等差数列： $\text {1 , 2 , 3 , .. , N }$ 他们两两之间的差： $\text { 2 - 1 , 3 - 2 , ... , N - ( N - 1 )}$ $\Leftrightarrow$ $\text {1 , 1 , 1 , ... , 1 }$ 我们发现，当他们两两作差之后，得到了一个全都相同的数列，我们把它称之为**常数数列** 同样的，我们把广泛定义的等差数列 ： $a_1 , a_2 , a_3 , .. , a_n \;$ 也两两作差 得到$\; a_2 - a_1 , a_3 - a_2 , ... \, , a_n - a_{n-1} \;$，记这个数列为$b_1 , b_2 , b_3 , .. , b_n \;$，简单记作{ ${b_n}$ } 由定义可知，他们的差也是相同的,既{ $b_n $ }是常数数列 对于一个数列 { $a_n$ } 来说，把数列 { $a_n$ } 的元素两两作差，得到数列 { $b_n$ } ，我们一般把这样的数列 { $b_n$ } 称为数列 { $a_n$ } 的**阶差数列**，记数列 { $b_n$ } 为数列 { $a_n$ } 的一阶差分，记作$\bigtriangleup f(x)=f(x+1)-f(x)$ 如果记该数列为 { $b_n$ }，其中 $ b_n = a_{n+1} - a_{n} $ ，再对数列 { $ b_n $ } 做差分，所得数列 $\; b_2 - b_1 , b_3 - b_2 , ... \, , b_n - b_{n-1} \;$ 称之为原数列 { $a_n$ } 的二阶差数列，记作$\bigtriangleup^{2} f(x)$， $\bigtriangleup^{2} f(x)$ $=\bigtriangleup (\bigtriangleup f(x)) $ $\qquad \quad \;$ $= \bigtriangleup(f(x+1)-f(x))$ $\qquad \quad \;$ $= ( f(x+2) - f(x+1) ) - ( f(x+1) - f(x) )$ $\qquad \quad \;$ $= f(x+2) - 2 * f(x+1) + f(x)$ 类似的，我们可以定义 $ \text {f(x)} $ 的二阶，三阶，...，$ \text {p} $ 阶差分 即$\bigtriangleup^{p} f(x) = \bigtriangleup (\bigtriangleup^{p-1} f(x) )$ 如果数列 { $ a_n $ } 的 $\text {p}$ 阶差数列是一个非$0$常数数列，那么称它为**p阶等差数列**.特别地，一阶等差数列就是我们通常说的等差数列，二阶及二阶以上的等差数列统称为高阶等差数列. **定理一：** 数列 {$ a_n $} 的是一个 $\text {p}$ 阶等差数列的充要条件是数列的通项 $a_n$ 为 $ \text {n} $ 的一个$\text {p} $ 次多项式. **证明：** 已知一个数列 { $ a_n $ } 的是一个 $\text {p}$ 阶等差数列，设数列 { $a_n$ } 的通项 $a_n$ 是一个关于 $\text {n}$ 的 $ \text {v} $ 次多项式，即 $f(x) = \sum\limits_{i=0}^{v}u_i*x^i$，其中 $u_i$ 为 $x^i$ 的系数 令数列 { $b_n$ }成为数列 { $ a_n $ } 的一次差分，则数列 { $b_n$ } 的通项公式为 $\bigtriangleup f(x) = f(x+1) - f(x)$ $\qquad \quad $ $= \sum\limits_{i=0}^{v}u_i*(x+1)^i - \sum\limits_{i=0}^{v}u_i*x^i$ 这里我们只考虑 $x^v$ ，易知只有 $ [i==v] $ 的情况才可能得到 $x^v$ $\qquad \quad $ $= u_v * (x+1)^v - u_v * x^v$ 显然 $(x+1)^v$ 可用二项式定理拆开，但我们只考虑 $x^v$ ，而 $(x+1)^v$ 拆开后 $x^v$ 的系数显然是 $1$ $\qquad \quad $ $= u_v * x^v - u_v * x^v$ $\qquad \quad $ $= 0$ 我们发现，数列 { $b_n$ } 的通项公式中 $x^v$ 被相减消除了，所以说，数列 { $b_n$ } 的通项公式 $b_n$ 是一个关于 $n$ 的 $v-1$ 次多项式。**也就是说，做一次差分之后数列的通项公式的多项式次数会-1** 由定义可知，数列 { $ a_n $ } 的 $\text {p}$ 阶差数列是一个非$0$常数数列，所以数列 { $a_n$ } 在做 $\text {p}$ 次差分后，得到一个 $0$ 次多项式，即数列 { $a_n$ } 的通项 $a_n$ 是一个关于 $n$ 的 $\text {p}$ 次多项式 证毕。 接下来回到题面上，由题意可知数列 { $a_n$ } 为： ${\sum\limits_{i=1}^{0}i^k},{\sum\limits_{i=1}^{1}i^k},{\sum\limits_{i=1}^{2}i^k}, \; ... \; ,{\sum\limits_{i=1}^{n}i^k}$ 我们把他们作差得到 ${\sum\limits_{i=1}^{1}i^k}-{\sum\limits_{i=1}^{0}i^k},{\sum\limits_{i=1}^{2}i^k}-{\sum\limits_{i=1}^{1}i^k}, {\sum\limits_{i=1}^{3}i^k}-{\sum\limits_{i=1}^{2}i^k}, \; ... \; ,{\sum\limits_{i=1}^{n}i^k}-{\sum\limits_{i=1}^{n-1}i^k}$ 即 $1^k,2^k, ... \, ,n^k $ 显然的，这个数列的通项公式为 $f(x) = x^k$ ， 是一个 $k $ 次多项式 数列 { $ a_n $ } 做一次差分后得到一个 $k$ 次多项式，所以数列 { $ a_n $ } 的通项 $a_n$ 是一个关于 $n$ 的 $k+1$ 次多项式 到了这里，我们终于证明了 $ \sum\limits_{i=1}^N {i^k}$ 是关于 $N$ 的 $\text{k+1} $ 次多项式 接下来的内容其他大佬的题解也有所说明，我这里谈谈我的做法 首先我们证明了这是一个 $k+1$ 次多项式，但是我们没有确定其系数，于是我们考虑拉格朗日插值 由于需要 $k+2$ 个点值才能确定 $k+1$ 次多项式，所以我们至少要取 $k+2$ 个点 这样一来暴力插值的复杂度为 $O (k^2)$，显然不能做到 $1e6$ 但是我们发现题目中有个很好的性质，就是他的点值不是确定的，而是我们可以随意选取，于是我们可以选取一些有特殊性质的点来考虑进行优化 于是我们选取一段连续的点，从 $1$ 开始连续选取 $k+2$个点，那么点集为 $\{ (i,\sum\limits_{j=1}^{i}j^k) | i \in [1,k+2] \} $ 先考虑一个点 $(x,\sum\limits_{i=1}^{x}i^k)$ 那么$ \sum\limits_{i=1}^{x}i^k = a_x * \prod\limits_{i=1,i\not=x}^{k+2}(x-i)$，其中 $a_i$ 为常数 即$ a_x = \dfrac{\sum_{i=1}^{x}i^k}{ \prod_{i=1,i\not=x}^{k+2}(x-i)}$ 对答案的贡献： $ ans_x = a_x * \prod\limits_{i=1,i\not=x}^{k+2}(N-i)$ $\qquad \,$ $ = \dfrac{\sum_{i=1}^{x}i^k}{ \prod_{i=1,i\not=x}^{k+2}(x-i)} * \prod\limits_{i=1,i\not=x}^{k+2}(N-i) $ $\qquad \,$ $= \dfrac{\sum_{i=1}^{x}i^k}{ \prod_{i=1}^{x-1}(x-i) * \prod_{i=x+1}^{k+2}(x-i)} * \prod\limits_{i=1,i\not=x}^{k+2}(N-i) $ $\qquad \,$ $= \dfrac{\sum_{i=1}^{x}i^k}{ \prod_{i=1}^{x-1}i * \prod_{i=1}^{k+2-x}(-i)} * \prod\limits_{i=1,i\not=x}^{k+2}(N-i) $ 显然对于 $ {\sum_{i=1}^{x}i^k} $ 来说我们可以递推+快速幂求出，对于 $\prod_{i=1}^{x-1}i$ 和 $\prod_{i=1}^{k+2-x}(-i)$ 来说我们只要预处理 $1$ 到 $k+2$ 的前缀积，最后再讨论 $k+2-x$ 的奇偶性即可。对于 $\prod\limits_{i=1,i\not=x}^{k+2}(N-i) $ 来说，这就相当于 $\prod\limits_{i=1}^{k+2}(N-i) $ 再乘上 $(N-x)$ 的逆元， $O(k \,log \, k )$ 暴力求逆元或 $O(k)$ 预处理线性求逆元都可以 最后的时间复杂度其实不管怎样还会是 $O(k \,log \, k )$ 的，因为递推+快速幂求 $ {\sum_{i=1}^{x}i^k} $的时候快速幂需要 $O(log\,k)$ 的时间复杂度 由于本人码风过丑，这里就不贴出来了，其他几位大佬的 $Code$ 都写的很清晰的