题解 CF622F 【The Sum of the k-th Powers】

Hexarhy

2021-06-08 23:31:00

Solution

### 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; } ```