Поиск n-го числа фибров, в O (logn)

Question

Я пытаюсь решить эту проблему: SPOJ problem.

И после некоторых исследований выяснилось, что это сводится к простому вычислению n-го числа фидов, однако n может стать действительно большим, поэтому решение O (n) не принесет пользы. Погуглить вокруг, я обнаружил, что вы можете вычислить п-е число Фибоначчи в O (LogN), а также пример кода, который делает именно то, что:

long long fibonacci(int n) 
{ 
    long long fib[2][2]= {{1,1},{1,0}},ret[2][2]= {{1,0},{0,1}},tmp[2][2]= {{0,0},{0,0}}; 
    int i,j,k; 
    while(n) 
    { 
     if(n&1) 
     { 
      memset(tmp,0,sizeof tmp); 
      for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++) 
         tmp[i][j]=(tmp[i][j]+ret[i][k]*fib[k][j]); 
      for(i=0; i<2; i++) for(j=0; j<2; j++) ret[i][j]=tmp[i][j]; 
     } 
     memset(tmp,0,sizeof tmp); 
     for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++) 
        tmp[i][j]=(tmp[i][j]+fib[i][k]*fib[k][j]); 
     for(i=0; i<2; i++) for(j=0; j<2; j++) fib[i][j]=tmp[i][j]; 
     n/=2; 
    } 
    return (ret[0][1]); 
} 

Я попытался изменить его проблемы, и я все еще получаю WA: http://ideone.com/3TtE5m

Я неправильно вычисляю модульную арифметику? Или это еще одна проблема?

Answer 1

Вы имеете в виду n-й фибоначчи, я надеюсь.

Для этого вам понадобится матричная декомпозиция чисел фибоначчи, описанных here.

Основная идея взять форму единичная матрица Дональда Кнута для ряда Фибоначчи, которая:

И вместо вычисления чисел fibonnaci традиционным способом вы будете пытаться найти матрица до степени (k), где k задано число.

Так что это решение проблемы при умножении матрицы k, не очень полезно, поскольку мы можем сделать это гораздо проще.

Но подождите! Мы можем оптимизировать матричное умножение. Вместо того, чтобы делать умножение k, мы можем сначала его квадратировать, а затем выполнить половину умножения. И мы можем продолжать это делать. Поэтому, если заданное число равно 2^а, мы можем сделать это за один шаг. Сохраняя квадрат матрицы.

Если матрица не является квадратом, мы можем сделать двоичное разложение числа и посмотреть, следует ли взять данную квадратную матрицу в конечный продукт или нет.

В вашем случае после каждого умножения вам также необходимо применить оператор modulo 123456 к каждому номеру матрицы.

Надеюсь, что мое объяснение поможет, если не увидеть ссылку для более четкой и более длинной.

На самом деле есть еще одно предостережение от задачи, так как вам предлагается указать число фибоначчи по модулю заданного числа. Вы также должны доказать, что получение напоминания о каждом матричном элементе не приводит к изменению операции. Другими словами, если мы умножаем матрицы и напоминаем, что мы на самом деле все еще получаем напоминания о числе фибоначчи. Но поскольку операция напоминания является дистрибутивной в дополнение и умножение, она фактически дает правильные результаты.

Answer 2

Существует очень простой алгоритм, используя только целые числа:

long long fib(int n) { 
    long long a, b, p, q; 
    a = q = 1; 
    b = p = 0; 
    while (n > 0) { 
     if (n % 2 == 0) { 
      long long qq = q*q; 
      q = 2*p*q + qq; 
      p = p*p + qq; 
      n /= 2; 
     } else { 
      long long aq = a*q; 
      a = b*q + aq + a*p; 
      b = b*p + aq; 
      n -= 1; 
     } 
    } 
    return b; 
} 

Это основано на identities of the Lucas sequence.