关于 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 等。
评论(10)