Skip to content

Instantly share code, notes, and snippets.

@osjayaprakash
Created December 21, 2012 19:18
Show Gist options
  • Save osjayaprakash/4355084 to your computer and use it in GitHub Desktop.
Save osjayaprakash/4355084 to your computer and use it in GitHub Desktop.
Matrix Exponentiation, Recurrence Eqn, Fibonacci
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const long long int mod = 1000000007;
class _matrix{
public:
long long int x[2][2];
int n,m;
_matrix() {
memset(x, 0, sizeof(x));
n=m=2;
}
void print(){
for(int i=0;i<2;i++){
for(int j=0;j<2;j++)
cout << x[i][j] << ' ';
cout << endl;
}
}
};
int N;
class _matrix mul(class _matrix a, class _matrix b)
{
class _matrix r;
for(int i=0;i<a.n;i++)
for(int j=0;j<a.m;j++)
{
unsigned long long res=0;
for(int k=0;k<b.n;k++)
res += 1LL*a.x[i][k]*b.x[k][j];
r.x[i][j] = res % mod;
}
return r;
}
class _matrix pow(class _matrix a, long long int n)
{
if(n==1)
return a;
class _matrix x = pow(a,n/2);
class _matrix r = mul(x,x);
if(n%2==1)
r=mul(r,a);
return r;
}
/*
fn(n)=fn(n)
fn(n+1)=fn(n) + fn(n-1)
1 1
1 0
1 1 a
1 0 b
1 1 a+b=c
1 0 a
1 1 c+a
1 0 c
*/
int main()
{
class _matrix a;
a.x[0][0]=1;
a.x[0][1]=1;
a.x[1][0]=1;
long long int tc, N;
cin >> tc;
while(tc--){
cin >> N;
class _matrix r1=pow(a,N+2);
//r.print();
//r1.print();
// FIB SEQ 1 1 2 3 5 8 13 21
// SUM OF FIRST N FIBO F(N+2)-1
// CURRENT SEQ 1 2 3 5 8 13 21
// SUM OF FIRST N CURR SEQ F(N+2)-2
long long res=r1.x[0][0] - 2;
if(res<0)
res+=mod;
cout << res << endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment