计算1 ^ X + 2 ^ X + ... + N ^ X mod 1000000007

Question

有没有算法算(1^x + 2^x + 3^x + ... + n^x) mod 1000000007？
注意:a^b是a的b次方.

约束是1 <= n <= 10^16, 1 <= x <= 1000.所以N的值非常大.

我只能解决O(m log m)if m = 1000000007.它非常慢,因为时间限制是2秒.

你有任何有效的算法吗？

有评论说它可能与这个问题重复,但它肯定是不同的.

Answer 1

你可以总结一下这个系列

1**X + 2**X + ... + N**X

在Faulhaber的公式的帮助下,你将得到一个具有X + 1计算任意的幂的多项式N.

如果您不想计算伯努利数,可以通过求解X + 2 线性方程(for N = 1, N = 2, N = 3, ..., N = X + 2)找到多项式,这是一种较慢的方法,但更容易实现.

我们有一个例子X = 2.在这种情况下,我们有一个X + 1 = 3有序多项式:

    A*N**3 + B*N**2 + C*N + D

线性方程是

      A +    B +   C + D = 1              =  1 
    A*8 +  B*4 + C*2 + D = 1 + 4          =  5
   A*27 +  B*9 + C*3 + D = 1 + 4 + 9      = 14
   A*64 + B*16 + C*4 + D = 1 + 4 + 9 + 16 = 30 

解决了我们得到的方程式

  A = 1/3
  B = 1/2
  C = 1/6
  D =   0 

最后的公式是

  1**2 + 2**2 + ... + N**2 == N**3 / 3 + N**2 / 2 + N / 6

现在,您所要做的就是在公式中添加任意大 N值.到目前为止,算法具有O(X**2)复杂性(因为它不依赖于N).