【笔记】求自然数幂和学习笔记

Author Avatar
Sakits 4月 02, 2018

简介

  顾名思义,自然数幂和就是求形如i=1nik\sum_{i=1}^n i^k的式子的值。
  持续更新中…学完一种更一种

倍增法

  设f(n,k)f(n,k)i=1nik\sum_{i=1}^n i^k
  若nn为奇数,则:

f(n,k)=f(n1,k)+nkf(n,k)=f(n-1,k)+n^k

  若nn为偶数,则:

f(n,k)=f(n/2,k)+i=n/2+1nik=f(n/2,k)+i=1n/2(i+n/2)k=f(n/2,k)+i=1n/2j=0k(kj)ij(n/2)kj=f(n/2,k)+j=0k(kj)i=1n/2ij(n/2)kj=f(n/2,k)+j=0k(kj)f(n/2,j)(n/2)kj\begin{aligned} f(n,k)&=f(n/2,k)+\sum_{i=n/2+1}^ni^k\\ &=f(n/2,k)+\sum_{i=1}^{n/2}(i+n/2)^k\\ &=f(n/2,k)+\sum_{i=1}^{n/2}\sum_{j=0}^{k}\binom{k}{j}i^j\cdot (n/2)^{k-j}\\ &=f(n/2,k)+\sum_{j=0}^k\binom{k}{j}\sum_{i=1}^{n/2}i^j\cdot (n/2)^{k-j}\\ &=f(n/2,k)+\sum_{j=0}^k\binom{k}{j}f(n/2,j)\cdot (n/2)^{k-j} \end{aligned}

  用这个方法求值复杂度O(k2logn)O(k^2logn),求多项式系数复杂度O(k2lognlogk)O(k^2lognlogk)

扰动法

  设Sk=i=1nikS_k=\sum_{i=1}^ni^k

Sk+(n+1)k=i=1n+1ik=i=0n(i+1)k=1+i=1n(i+1)k=1+i=1nj=0k(kj)ij=1+j=0k(kj)i=1nij=1+j=0k(kj)Sj\begin{aligned} S_k+(n+1)^k&=\sum_{i=1}^{n+1}i^k\\ &=\sum_{i=0}^n(i+1)^k\\ &=1+\sum_{i=1}^n(i+1)^k\\ &=1+\sum_{i=1}^n\sum_{j=0}^k\binom{k}{j}i ^j\\ &=1+\sum_{j=0}^k\binom{k}{j}\sum_{i=1}^ni^j\\ &=1+\sum_{j=0}^k\binom{k}{j}S_j \end{aligned}

  这时SkS_k不见了咋整…问题不大,稍微变一下就好了

Sk+1+(n+1)k+1=1+j=0k+1(k+1j)SjSk+1+(n+1)k+1=1+j=0k1(k+1j)Sj+Sk(k+1)+Sk+1(k+1)Sk=(n+1)k+1j=0k1(k+1j)Sj1Sk=(n+1)k+1j=0k1(k+1j)Sj1k+1\begin{gathered} S_{k+1}+(n+1)^{k+1}=1+\sum_{j=0}^{k+1}\binom{k+1}{j}S_j\\ S_{k+1}+(n+1)^{k+1}=1+\sum_{j=0}^{k-1}\binom{k+1}{j}S_j+S_k\cdot (k+1)+S_{k+1}\\ (k+1)S_k=(n+1)^{k+1}-\sum_{j=0}^{k-1}\binom{k+1}{j}S_j-1\\ S_k=\frac{(n+1)^{k+1}-\sum_{j=0}^{k-1}\binom{k+1}{j}S_j-1}{k+1} \end{gathered}

  用这个方法求值复杂度O(k2)O(k^2),求多项式系数使用高斯消元复杂度O(k3)O(k^3)
  自然数幂的变式也可以使用这个方法,见bzoj3516