¿Hay alguna manera de resolver los problemas del problema SEQ sin el uso de la exponenciación de matrices?

Answer 1

tl; dr: teóricamente sí, pero no creo que sea práctico debido a problemas de precisión

El caso de las recurrencias lineales se describe en este artículo: http://en.wikipedia.org/wiki/Rec…. Siempre que pueda encontrar raíces de polinomios, puede encontrar fácilmente la fórmula cerrada y obtener el enésimo elemento en tiempo constante (con algunos problemas de precisión, por supuesto). Bueno, en realidad, no siempre se obtiene una fórmula cerrada: algunas raíces no se pueden representar mediante operaciones simples (como raíces, división y números racionales). Pero puedes obtener algún tipo de aproximación.

Además, ni siquiera necesita que estas raíces sean racionales o reales; pueden ser complejas (si no me equivoco, me alegraría saber de alguien que esté más familiarizado con la generación de funciones, lo cual haré) . Y debido a que cualquier polinomio tiene exactamente N raíces complejas, puede encontrar una fórmula cerrada para cualquier recurrencia. Por supuesto, tendrás aún más problemas de precisión aquí.

Este enfoque se puede probar utilizando funciones generadoras (http://en.wikipedia.org/wiki/Gen…). Le permiten obtener una fórmula cerrada para el enésimo elemento. El ejemplo clásico es la fórmula de Binet para los números de Fibonacci. En realidad, son aún más potentes: puede generar secuencias dependientes cruzadas, secuencias que dependen de todos los números anteriores (en algunos casos).

Desafortunadamente, en ese problema tienes que calcular la respuesta precisa (bueno, los últimos nueve dígitos, pero eso no cambia mucho). Es decir, debe realizar cada paso con alta precisión. Probablemente necesite exponer a 10 ^ 9 de potencia, eso significa que debe almacenar 10 ^ 9 dígitos. No puede hacer cálculos fácilmente módulo 10 ^ 9 aquí, porque tiene números reales, no enteros.

Answer 2

Gracias por el A2A. No estoy seguro si entiendo tu pregunta. En los detalles de la pregunta, parece implicar que este problema no se puede resolver utilizando una exponenciación de matriz rápida. Ese no es el caso: con k siendo tan pequeño, es perfectamente factible resolverlo de esa manera. La complejidad temporal de tal solución sería solo [matemática] O (k ^ 3 \ log n) [/ matemática].

En mi respuesta, la respuesta de Michal Forišek a ¿Qué condición debe cumplirse para que una función recursiva pueda transformarse en una multiplicación matricial? Doy una descripción bastante detallada de cómo escribir tal solución.

Comenta si quieres algo más.

Answer 3

Gracias por el A2A. Definitivamente deberías leer la respuesta vinculada de Michal Forišek sobre la multiplicación de matrices, pero también señalaré que para problemas más antiguos como este, la gente a menudo publica código en GitHub. No abuses de ello. 🙂

venkatrn / SPOJ