FIBEASY Matrix Exponentiation Solution? O(lgn) (edit: this solution failed for subcase 3 Yet I am producing right answers?)

No idea how to write formatted code… but
here goes copy and paste

(ignore the power of two function, I was getting desparate and tried every possible thing)

My understanding is… I compared my code, to other “accepted” solutions (so like 10^18, 10^18-1, etc.)… to see where my code has failed. But the problem is… they give the same output? So now I’m wondering, where has my code fails in sub-task2… Because if it’s not failing for 10^18, how can it fail for other cases.

Please, I am a beginner and I really want help… (i know this isn’t the best solution, so don’t give me stuff like “hey better way to do this”. The problem I have isn’t not realizing or understanding the other solution. It’s more of… why does this not work?

I realized that if I make a fibonacci function that outputs the fib number n mod 10, and return the 2^(lgn) index (or something like that), it produces the right answer.

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int lli;


void multiply(lli F[2][2], lli M[2][2]); 
  
void power(lli F[2][2], lli n); 
lli poweroftwo(lli x)
{
    if(x == 0)
    {
        return 1;
    }
    else if(x%2 == 0)
    {
        return poweroftwo(x/2) * poweroftwo(x/2);
    }
    else
    {
        return 2 * poweroftwo(x/2) * poweroftwo(x/2);
    }
}



lli fibonacci(lli n) 
{ 
  lli F[2][2] = {{1,1},{1,0}}; 
  if (n == 0) 
    return 0; 
  power(F, n-1); 
  return F[0][0]; 
} 
  
/* Optimized version of power() in method 4 */
void power(lli F[2][2], lli n) 
{ 
  if( n == 0 || n == 1) 
      return; 
  lli M[2][2] = {{1,1},{1,0}}; 
  
  power(F, n/2); 
  multiply(F, F); 
  
  if (n%2 != 0) 
     multiply(F, M); 
} 
  
void multiply(lli F[2][2], lli M[2][2]) 
{ 
  lli x =  F[0][0]*M[0][0] % 10 + F[0][1]*M[1][0] %10; 
  lli y =  F[0][0]*M[0][1]%10 + F[0][1]*M[1][1]%10; 
  lli z =  F[1][0]*M[0][0]%10 + F[1][1]*M[1][0]%10; 
  lli w =  F[1][0]*M[0][1]%10 + F[1][1]*M[1][1]%10; 
  
  F[0][0] = x%10; 
  F[0][1] = y%10; 
  F[1][0] = z%10; 
  F[1][1] = w%10; 
} 


int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        lli x = log(n)/ log(2);
        lli index = poweroftwo(x);
        cout << fibonacci(index-1) << endl;
    }

   
}
1 Like

format - [Tutorial] CoLoR format the Code!

1 Like

The problem with your code is:

  1. The data-type of the variable n should be unsigned long long rather than int, look at the constraints given in the problem statement i.e 1 \leq n \leq 10^{18}. You cannot store that much larger value in an int variable.
  2. I ran your code to check whether it calculated the log(n) correctly or not, and I found out that its not.
    E.g. When I supply n = 4503599627370496 = 2^{52} your code is giving 52 that’s right but when I supply n = 4503599627370495 = 2^{52} - 1 your code is still giving me 52 which is wrong rather is should give me 51. This happens due to the precision error of the log() which you are using in your program.
    To solve this issue, use the log() function which takes data of type long double as input and returns a long double output.
    Change the instruction lli x = log(n) / log(2) to lli x = log2l(n)

There are many more changes in your code, refer to your updated code below:

    #include<bits/stdc++.h>
    #include<cmath>

    using namespace std;

    typedef unsigned long long lli;

    void multiply(lli F[2][2], lli M[2][2]); 
    void power(lli F[2][2], lli n);

    lli poweroftwo(lli x) {
        lli val;
        if(!x) {
            return 1;
        } else {
            val = poweroftwo(x / 2);
        }
        if(x & 1) {
            return (2 * val * val);
        } else {
            return (val * val);
        }
    }

    lli fibonacci(lli n) { 
      lli F[2][2] = {{1,1},
                    {1,0}}; 
      if (n == 0) 
        return 0; 
      power(F, n-1); 
      return F[0][0]; 
    } 
      
    /* Optimized version of power() in method 4 */
    void power(lli F[2][2], lli n) { 
      if( n == 0 || n == 1) 
          return; 
      lli M[2][2] = {{1,1},
                    {1,0}}; 
      power(F, n/2);
      multiply(F, F);
      if (n & 1) {
          multiply(F, M);
      }
    }
      
    void multiply(lli F[2][2], lli M[2][2]) { 
      lli x = (F[0][0] * M[0][0]) + (F[0][1] * M[1][0]);
      lli y = (F[0][0] * M[0][1]) + (F[0][1] * M[1][1]);
      lli z = (F[1][0] * M[0][0]) + (F[1][1] * M[1][0]);
      lli w = (F[1][0] * M[0][1]) + (F[1][1] * M[1][1]);
      F[0][0] = x % 10; 
      F[0][1] = y % 10; 
      F[1][0] = z % 10; 
      F[1][1] = w % 10; 
    } 

    int main(void) {
        int t;
        cin >> t;
        assert(t > 0);
        while(t--)
        {
            lli n,x,index;
            cin >> n;
            assert(n > 0);
            if(n & (n - 1)) {
                x = log2l(n);
                // x = log10l(n)/log10l(2);
                index = poweroftwo(x);
            } else {
                index = n;
            }
            cout << fibonacci(index-1) << endl;
        }
        return 0;
    }

The above code is accepted!

NOTE:
You don’t need to use matrix exponentiation to solve this problem, just use the fact that Fibonacci sequence have a period denoted by \pi(n) known as Pisano Period when the members of the sequence is taken modulo some number.
For this problem \pi(n = 10) = 60. Use this information to solve the problem.
You can look at the code & editorial written by me by clicking on the link Easy Fibonacci.

2 Likes

Have a look over this ( below ) solution and try to generate the failed test cases by yourself.
https://www.codechef.com/viewsolution/26324893

It fails for the testcase

1
2147483648

(the answer should be 3).

1 Like

Matrix Exponential solution::
https://www.codechef.com/viewsolution/26256246

You should replace your multiply and power function with builtin function exp2l() and log2l() respectively.

n = log2l(n);
n = exp2l(n) - 1;
cout << f[n % 60] << "\n";
Full Solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  int f[60] = {0};
  f[1] = 1;
  for (int i = 2; i <= 60; i++) {
    f[i] = (f[i - 1] + f[i - 2]) % 10;
  }

  int t; cin >> t;
  while (t--) {
    ull n; cin >> n;
    n = log2l(n);
    n = exp2l(n) - 1;
    cout << f[n % 60] << "\n";
  }
  return 0;
}