SubArray Somme de Fibonacci Numéro

Question

J'ai un tableau A de N nombres. Je dois trouver la somme des nombres de Fibonacci de la somme de tous ses sous-réseaux. Par exemple:

A = {1,1} 
F[Sum A[1,1]] = F[1] = 1 
F[Sum A[1,2]] = F[2] = 1 
F[Sum A[2,2]] = F[1] = 1 
Ans = 1 + 1 + 1 = 3 

La question est semblable à un this, mais je dois calculer la somme d'une séquence standard de Fibonacci. Voici le source code.

Quelle propriété est utilisée ici?
Quelqu'un peut-il expliquer les mathématiques derrière tout ça? Comment éviter une solution O(N^2)? Comment modifier le code source des numéros Fibonacci standard?

Answer 1

Voici une solution qui fonctionne dans O(N * log MAX_A * k^3) temps (où MAX_A est la valeur maximale du tableau et k est le nombre de variables utilisées dans la formule récursive (son égale à 2 pour fibonacci et 3 pour le problème de votre lié à votre . question) Je ne vais pas faire référence au code source que vous avez fourni comme il est assez difficile à lire, mais il semble que il utilise des idées similaires:

1. apprenons comment calculer le i-th nombre de Fibonacci rapidement il est facile de. voir que f(i) = F^n * [1, 1].transposed(), où F est une matrice [[1, 1], [1, 0]] (il serait b e [[1, 1, 1], [1, 0, 0], [0, 0, 1]] pour le problème d'origine. Nous pouvons trouver la puissance n-th d'une matrice rapidement en utilisant l'exponentiation binaire.

2. Développons cette idée. En termes de matrices, on nous demande d'évaluer l'expression suivante:

   sum for all valid L, R of ((F^(a[L] + ... + a[R]) * [1, 1].transposed())[0]) 
   

   ou, ce qui revient (comme la multiplication de matrices est distributive par rapport à l'addition)

   ((sum for all valid L, R of F^(a[L] + ... + a[R])) * [1, 1].transposed())[0] 
   

3. Maintenant, nous avons besoin de comprendre comment calculer cette somme efficacement. Apprenons à le faire progressivement. Supposons que toutes les sous-matrices qui se terminent dans une position n ou plus petite ont déjà été traitées et nous voulons ajouter la suivante. Selon l'énoncé du problème, nous devrions ajouter F^a[n + 1] + F^(a[n + 1] + a[n]) + ... + F^(a[n + 1] + a[n] + ... + a[0]) à la réponse, qui est égale à F^a[n + 1] * (F^a[n] + F^(a[n] + a[n - 1]) + ... + F^(a[n] + a[n - 1] + ... + a[0])).

4. C'est tout. Nous avons déjà une solution efficace. Voici un code pseudo:

   pref_sum = I // identity matrix. This variable holds the second 
   // term of the product used in step 3 
   total_sum = zeros // zero matrix of an appropriate size 
   // It holds the answer to the problem 
   for i = 0 .. N - 1 
       cur_matrix = binary_exponentiation(F, a[i]) // A matrix for the a[i]-th fibonacci number 
       // Everything is updated according to the formulas shown above 
       total_sum += pref_sum * cur_matrix 
       pref_sum = pref_sum * cur_matrix + I 
   // Now we just need to mulitiply the total_sum by an appropriate vector 
   // which is [1, 1].transposed() in case of Fibonacci numbers 
   

5. Si l'on suppose que la taille de la matrice F est constante (il est, encore une fois, 2 en cas de nombres de Fibonacci), la complexité de temps est O(N * (log MAX_A + const)) = O(N * log MAX_A) car il n'y a qu'un seul exponentiation binaire pour chaque élément du tableau original suivi d'un nombre constant de multiplications matricielles et d'additions.