自然幂数和

\[\sum_{i=1}^ni^k \]

  1. 递推

    令其为\(f(n,k)\)

    \[(i+1)^{k+1}-i^{k+1}=C_{k+1}^1i^k+C_{k+1}^2i^{k-1}+…+C_{k+1}^ki+1 \]

    相加得

    \[(n+1)^{k+1}-1=C_{k+1}^1\sum_{i=0}^ni^k+C_{k+1}^2\sum_{i=0}^ni^{k-1}+…+C_{k+1}^k\sum_{i=0}^ni+n \]

    \[f(n,k)=\frac1{k+1}((n+1)^{k+1}-\sum_{i=2}^{k+1}C_{k+1}^if(n,k+1-i)-1) \]

    时间复杂度\(O(k^2)\)

  2. 拉格朗日插值

    明显是一个关于n的k+1次多项式,可以做到\(O(k)\)

  3. 斯特林数(见组合数学

  4. 伯努利数

    \[f(n,k)=\frac1{k+1}\sum_{i=1}^{k+1}C_{k+1}^iB_{k+1-i}(n+1)^i \]

    \(B_0=1\),对于\(n>0\)有

    \[\sum_{i=0}^nC_{n+1}^iB_i=0 \]

  5. 多项式差分

    \(g(n)=n^k\)这一函数的差分表的第0条对角线为\(c_0…c_k\)

    \[\sum_{i=0}^nf(i)=\sum_{i=0}^n\sum_{j=0}^kc_jC_i^j \]

    \[=\sum_{j=0}^k\sum_{i=0}^nc_jC_i^j \]

    \[=\sum_{j=0}^kc_jC_{n+1}^{j+1} \]

上一篇:为什么不能直接调用DbContext.ObjectContext 获取属性呢?


下一篇:运算放大器