Эффективное решение для моей задачи нужно

Question

я просто решить эту проблему, но хотите знать, более эффективный способ сделать матричное умножение

M = | 1 0 3 | 
    | 1 0 2 | 
    | 0 5 0 | 

е [п] = М^п

я реализовал с помощью Exponentiation_by_squaring

Есть ли более эффективные, чем это?

Answer 1

Я думаю, это на самом деле больше подходит для математики, так как существует закрытое решение формы. Это система Linear homogeneous recurrence relations with constant coefficients.

Другой вешать: Вы можете ускорить программу дважды, выводя формулу для двух стадий, то есть выразить RR(i) и т.д. с помощью RR(i-2) и т.д.

И это может повторяться, так что вы можете прыгать гораздо быстрее.

Answer 2

Одна из проблем заключается в том, что ваши вычисления переполнены. Если вы запустите его для K = 1 и J = 9, вы получите -334328541#510576792#-817751931.
Самое легкое исправление для этого должно сделать % 1000000006 в calculateProduction.

Об эффективности, я бы рассматривал эту проблему как выполнение матричных умножений. Вы начинаете с вектором (то есть 1 * 3 матрицы):

3 1 0 

И на каждом шаге вы умножаете его (по модулю 1000000006) с матрицей:

1 1 0 
0 0 5 
3 2 0 

Давайте назовем вектор V и матрицы M. В основном вам необходимо рассчитать V * M ^N. Так как умножение матриц ассоциативно, вы можете вычислить M ^N первый, и сделать это рекурсивно:
M ^N = (M ^N/2) если N четно, или
M ^N = M * (M ^[N/2]) если N нечетно

Answer 3

Вам не нужно вычислить ММ. Вот почему:

PP[i] = 5*MM[i-1] = 5*(RR[i-2] + 2*PP[i-2]) 
RR[i] = RR[i-1] + 3*PP[i-1] = (RR[i-2] + 3*PP[i-2]) + 3*PP[i-1] 

См.? Вам не нужно вычислять ММ на каждом шаге. Это должен быть алгоритм:

public class RecurrenceMachine { 
    private static final int max = 1000000006; 

    public String calculate(int k, int j) { 
     long n = k * j; 
     if (n < 1) 
      return "error"; 
     long RRi2 = 3; 
     long PPi2 = 0; 
     long RRi1 = 3 + 3 * PPi2; 
     long PPi1 = 5 * 1; 
     if (n == 1) 
      return RRi1 + "##" + (RRi2 + 2 * PPi2) + "##" + PPi1; 
     Long PPi = (long) 0, RRi = (long) 0, temp; 
     int i; 
     for (i = 2; i <= n; i++) { 
      temp = RRi2 + 2 * PPi2; 
      PPi = 5 * temp; 
      if (PPi >= max) 
       PPi %= max; 
      RRi = temp + PPi2 + 3 * PPi1; 
      if (RRi >= max) 
       RRi %= max; 
      RRi2 = RRi1; 
      PPi2 = PPi1; 
      RRi1 = RRi; 
      PPi1 = PPi; 
     } 
     return RRi + "##" + (RRi2 + 2 * PPi2) % max + "##" + PPi1; 
    } 
} 

Я пробовал только с небольшими значениями и, похоже, сработал.