Discussion About FIBOSUM

#1

This is Discussion thread about FIBOSUM

#2 
#include<bits/stdc++.h>
using namespace std;
unsigned long long fib(int n) { 
 double phi = (1 + sqrt(5)) / 2; 
unsigned long long ans = round(pow(phi, n) / sqrt(5));
return ans%1000000007; 
}  
int main() {
int q;
cin>>q;
for(int i=0;i<q;i++){
	int s,e;
	cin>>s>>e;
	unsigned long long a= (fib(e+2));
	unsigned long long b= (fib(s+1));
	cout<<(a-b)%1000000007<<endl;
}

}

This code is not working, can someone tell me how to solve this problem…

#3

@namananeja1985
I think trying long long int may help in the initialisation of s and e variables.
Because it is mentioned n and m are atmost 1e9.

#4

Matrix exponentiation on Recurrence of Fibonacci Sum
My recurrence came out as Sn=Sn-1 + Fn-2 + Fn-1
Transformation matrix was

  • [111]
  • [001]
  • [011]
    Initial vector -
    1
    0
    1
    Getting WA in 4 cases . Cans anyone see the problem?

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long int lli;
typedef vector < vector< lli> > vvi;
vector < lli > F1(3);
void assign()
{ // making transformation matrix and initial vector
F1[0] = 1;
F1[1] = 0;
F1[2] = 1;
}
vvi multiply(vvi A,vvi B)
{ vvi X (3,vector (3));
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
for(int x=0;x<3;x++)
{
X[i][j] = (X[i][j]%mod+((A[i][x]%mod)*(B[x][j]%mod))%mod)%mod;
}
}
}
return X;
}
vvi power(vvi T,lli n)
{
if(n==1)
return T;
if(n&1)
{
return multiply(T,power(T,n-1));
}
else
{
vvi X = power(T,n/2);
return multiply(X,X);
}
}
lli compute(lli n)
{
if(n==0)
return 0;
if(n==1)
return 1;
// STEP 1-> make initial vector-> done in assign() function
//STEP 2-> make transormation matrix
vvi T (3,vector(3));
T[0][0]=1;
T[0][1]=1;
T[0][2]=1;

T[1][0]=0;
T[1][1]=0;
T[1][2]=1;

T[2][0]=0;
T[2][1]=1;
T[2][2]=1;
// STEP 3 Calculate power
T = power(T,n-1);
// Step 4 Calculate answer
lli res = 0;
for(int i=0;i<3;i++)
{
    res = (res%mod+ ((T[0][i]%mod)*F1[i])%mod)%mod;
}
return res; }

int main()
{ ios::sync_with_stdio(0);
lli t;
cin>>t;
assign();
while(t–)
{
lli n,m;
cin>>n>>m;
if(n==m)
{
cout<<0<<endl;
continue;
}
if(n<m)
{
if(n==0)
cout<<compute(m)<<endl;
else{
cout<<(compute(m)%mod-compute(n-1)%mod + mod)%mod<<endl;
}
}
else
{
if(m==0)
cout<<compute(n)<<endl;
else
{
cout<<(compute(n)%mod - compute(m-1)%mod + mod)%mod<<endl;
}
}
}
return 0;
}