Lflame

关于 sigma( i^d ) 的一些东西 !

    令 S(n) = sigma(1<= i <=n | i^d ) , S(n)要怎么求呢  ?

    首先...矩阵快速幂当然可以搞过....不过显然要讲的并不是它...

    接下来切入正题。

    S(n) 可以写成 sigma(0<=i<=d+1  |  ai * n^i) 。  也就是说,可以把 S(n)看作一个 d+1 次的多项式 。

    于是,我们可以带入 d+2 个方程用高消将 ai 全部解出 。


    可是这个比起矩阵快速幂有什么优势呢 ?  当然是有的,对于一些题目,可以通过这个变形来化简式子 ! 比如说 bzoj 3601 等。

评论(11)