计算1 ^ X + 2 ^ X + ... + N ^ X mod 1000000007 [英] Calculating 1^X + 2^X + ... + N^X mod 1000000007

问题描述

有什么算法可以计算（1 ^ x + 2 ^ x + 3 ^ x + ... + n ^ x）mod 1000000007 吗？

注意： a ^ b 是a的b次方。

Is there any algorithm to calculate (1^x + 2^x + 3^x + ... + n^x) mod 1000000007?
Note: a^b is the b-th power of a.

约束是 1 <= n <= 10 ^ 16，1 <= x< = 1000 。因此，N的值非常大。

The constraints are 1 <= n <= 10^16, 1 <= x <= 1000. So the value of N is very large.

如果<<，我只能求解 O（m log m） code> m = 1000000007 。这很慢，因为时间限制为2秒。

I can only solve for O(m log m) if m = 1000000007. It is very slow because the time limit is 2 secs.

您有任何有效的算法吗？

Do you have any efficient algorithm?

有一条评论，它可能是此问题的重复项，但这绝对是

There was a comment that it might be duplicate of this question, but it is definitely different.

推荐答案

您可以总结系列

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

在 Faulhaber公式的帮助下，

将得到具有 X +1的幂的多项式，以计算任意 N 。

如果不想计算伯努利数，则可以通过求解 X + 2来找到多项式 线性方程（对于 N = 1，N = 2，N = 3，...，N = X + 2 ），这是一种较慢的方法，但更易于实现。

If you don't want to compute Bernoulli Numbers, you can find the the polynomial by solving X + 2 linear equations (for N = 1, N = 2, N = 3, ..., N = X + 2) which is a slower method but easier to implement.

让我们举一个 X = 2 的示例。在这种情况下，我们有 X +1 = 3 阶多项式：

Let's have an example for X = 2. In this case we have an X + 1 = 3 order polynomial:

    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 

已经解决了方程，我们将得到

Having solved the equations we'll get

  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 ）。

Now, all you have to do is to put an arbitrary large N into the formula. So far the algorithm has O(X**2) complexity (since it doesn't depend on N).

这篇关于计算1 ^ X + 2 ^ X + ... + N ^ X mod 1000000007的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！