algorithm - Cálculo de 1 ^ X+2 ^ X+…+N ^ X mod 1000000007

7 mod 5

Question

¿Hay algún algoritmo para calcular (1^x + 2^x + 3^x + ... + n^x) mod 1000000007 ?
Nota: a^b es la b-th potencia de a.

Las restricciones son 1 <= n <= 10^16, 1 <= x <= 1000 . Entonces el valor de N es muy grande.

Solo puedo resolver para O(m log m) si m = 1000000007 . Es muy lento porque el límite de tiempo es de 2 segundos.

¿Tienes algún algoritmo eficiente?

Hubo un comentario que podría ser duplicado de esta pregunta , pero definitivamente es diferente.

Answer 1

Creo que la respuesta de Vatine es probablemente el camino a seguir, pero ya escribí esto y puede ser útil, para este o para el problema similar de otra persona.

No tengo tiempo esta mañana para una respuesta detallada, pero considere esto. 1^2 + 2^2 + 3^2 + ... + n^2 tomaría O ( n ) pasos para calcular directamente. Sin embargo, es equivalente a (n(n+1)(2n+1)/6) , que se puede calcular en tiempo O (1). Existe una equivalencia similar para cualquier potencia integral superior x .

Puede haber una solución general a tales problemas; No sé de uno, y Wolfram Alpha tampoco parece saber de uno. Sin embargo, en general, la expresión equivalente es de grado x + 1 , y se puede calcular calculando algunos valores de muestra y resolviendo un conjunto de ecuaciones lineales para los coeficientes.

Sin embargo, esto sería difícil para una x grande, como 1000 como en su problema, y ​​probablemente no se pueda hacer en 2 segundos.

¿Quizás alguien que sepa más matemáticas que yo pueda convertir esto en una solución viable?

Edit: Vaya, veo que Fabian Pijcke ya había publicado un enlace útil sobre en.wikipedia.org/wiki/Faulhaber''s_formula antes de publicar.

Answer 2

Hay algunas formas de acelerar la exponenciación modular. De aquí en adelante, usaré ** para denotar "exponentiate" y % para denotar "módulo".

Primero algunas observaciones. Siempre es el caso que (a * b) % m es ((a % m) * (b % m)) % m . También ocurre siempre que a ** n es lo mismo que (a ** floor(n / 2)) * (a ** (n - floor(n/2)) . Esto significa que para un exponente <= 1000, siempre podemos completar la exponenciación en un máximo de 20 multiplicaciones (y 21 mods).

También podemos omitir algunos cálculos, ya que (a ** b) % m es lo mismo que ((a % m) ** b) % m y si m es significativamente menor que n, simplemente tenemos múltiples sumas que se repiten, Con una "cola" de una repetición parcial.

Answer 3

Puedes resumir la serie.

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

con la ayuda de la fórmula de Faulhaber y obtendrás un polinomio con una potencia X + 1 para calcular N arbitraria.

Si no desea calcular los números de Bernoulli , puede encontrar el polinomio resolviendo las ecuaciones lineales X + 2 (para N = 1, N = 2, N = 3, ..., N = X + 2 ), que es Un método más lento pero más fácil de implementar.

Tengamos un ejemplo para X = 2 . En este caso tenemos un polinomio de orden X + 1 = 3 :

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

Las ecuaciones lineales son

      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 

Habiendo resuelto las ecuaciones obtendremos

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

La formula final es

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

Ahora, todo lo que tiene que hacer es poner una N grande arbitraria en la fórmula. Hasta ahora, el algoritmo tiene complejidad O(X**2) (ya que no depende de N ).