题解 CF622F 【The Sum of the k-th Powers】
Hexarhy
2021-06-08 23:31:00
### Preface
拉格朗日插值初步应用。[具体介绍戳这](https://www.luogu.com.cn/blog/80049/lagrange-interpolation-basis)。
这里提供一个较为感性但非常简单的证明方法。
### Solution
本题引出了一个重要的数学结论:$S_k(n)$ 是一个关于 $n$ 的 $k+1$ 次多项式。
如果能直接解出这个多项式计算,当然可以。但我们用拉格朗日插值就可以避免繁琐的推导,隐式地计算这个多项式。
现在来证明 $S_k(n)$ 是一个多项式。
已知 $S_1(n)=\dfrac{n(n+1)}{2}$,以此为基础进行归纳推导。
$$
\begin{aligned}
S_{k+1}(n)&=\sum_{i=1}^ni^{k+1}\\
&=\sum_{i=1}^n i\cdot i^k\\
&=n\sum_{i=1}^n i^k-\sum_{i=1}^{n-1}i^k-\sum_{i=1}^{n-2}i^k-\cdots-1^k\\
&=nS_k(n)-\sum_{i=1}^{n-1}S_k(i)
\end{aligned}
$$
虽然我们没有求出通项公式,但是根据递推式我们知道,$S_1(n)$ 是多项式,多项式加法和乘法的结果也是多项式,也就是说,$S_k(n)$ 也是多项式。
同时,递推公式也反映出了 $S_{k}(n)$ 的次数是 $k+1$ 次,因为 $S_1(n)$ 是二次的。
既然如此,我们就可以用拉格朗日插值,取 $x_{i}=\{1,2,3\cdots,k+2\}$ 即可求出 $S_k(n)$。
$$
S_k(n)=\sum_{i=1}^{k+2}S_{k}(i)\prod_{j\neq i}^{k+2}\frac{n-j}{i-j}
$$
当然,如果直接按照公式算是 $O(k^2)$ 的。但是我们取的特殊值可以提供简化。运用[乘法逆元 2](https://www.luogu.com.cn/problem/P5431) 的套路,预处理出前缀积,后缀积,阶乘即可。
时间复杂度 $O(k\log p)$,$p$ 为模数。
### Code
```cpp
int main()
{
read(n,k);
prod1[0]=fact[0]=prod2[k+3]=1;
for(int i=1;i<=k+2;i++) fact[i]=fact[i-1]*i%MOD;//预处理阶乘
for(int i=1;i<=k+2;i++) prod1[i]=prod1[i-1]*(n-i+MOD)%MOD;//预处理前缀积
for(int i=k+2;i>=1;i--) prod2[i]=prod2[i+1]*(n-i+MOD)%MOD;//预处理后缀积
for(int i=1;i<=k+2;i++) sum[i]=(sum[i-1]+qpow(i,k))%MOD;//预处理 S_k(i)
auto inv=[=](const ll& a){return qpow(a,MOD-2);};//求逆元
for(int i=1;i<=k+2;i++)
{
ll t=prod1[i-1]*prod2[i+1]%MOD;
ll t2=(fact[i-1]*fact[k+2-i]%MOD*((k-i)&1?-1:1)+MOD)%MOD;
ans=(ans+sum[i]*t%MOD*inv(t2)%MOD)%MOD;
}
cout<<ans<<endl;
return 0;
}
```