CF622F The Sum of the k-th Powers题解

formkiller · 2019-12-06 16:58:27 · 题解

写在前面的话

由于本菜鸡数学水平过差，在写这题的时候不懂为什么 \sum\limits_{i=1}^N {i^k} 是 \text{k+1} 次多项式，在做完之后希望可以帮助到像我一样数学不好的同学，所以本文主要证明 \sum\limits_{i=1}^N {i^k} 是 \text{k+1} 次多项式 知道的大佬们直接跳过好了

简单证明

参考资料：《数学奥林匹克竞赛小丛书（第二版） 高中卷6 -- 数列与数学归纳法》

首先看一个最基本的等差数列：

他们两两之间的差：

我们发现，当他们两两作差之后，得到了一个全都相同的数列，我们把它称之为常数数列

同样的，我们把广泛定义的等差数列 ：

如果记该数列为 { 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)，

类似的，我们可以定义 \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 } 的通项公式为

这里我们只考虑 x^v ，易知只有 [i==v] 的情况才可能得到 x^v

显然 (x+1)^v 可用二项式定理拆开，但我们只考虑 x^v ，而 (x+1)^v 拆开后 x^v 的系数显然是 1

我们发现，数列 { 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 } 为：

我们把他们作差得到

即 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)}

对答案的贡献：

显然对于 {\sum_{i=1}^{x}i^k} 来说我们可以递推+快速幂求出，对于 \prod_{i=1}^{x-1}i 和 \prod_{i=1}^{k+2-x}(-i) 来说我们只要预处理 1 到 k+2 的前缀积，最后再讨论