➤ Problem Link : FIBOSUM
👉 Hint : edit please
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll mod = 1000000007;
ll base[2][2]={{1,1},{1,0}};
ll ans[2][2];
ll val=0;
ll n,m;
void multiply(ll a[2][2],ll b[2][2])
{
ll v,c[2][2];
for(ll i=0;i<2;i++)
{
for(ll j=0;j<2;j++)
{
c[i][j]=0;
v=0;
for(ll k=0;k<2;k++)
v+=(a[i][k]*b[k][j])%mod;
c[i][j]=v%mod;
}
}
for(ll i=0;i<2;i++)
{
for(ll j=0;j<2;j++)
{
a[i][j]=c[i][j];
}
}
}
void power(ll a)
{
if(a==0)
return;
power(a/2);
multiply(ans,ans);
if(a%2==1)
multiply(ans,base);
}
int main()
{
int t;
cin>>t;
while(t--)
{
ans[0][0]=1;
ans[0][1]=0;
ans[1][0]=0;
ans[1][1]=1;
val=0;
cin>>n>>m;
power(m+1);
ll a1=ans[0][0];
ans[0][0]=1;
ans[0][1]=0;
ans[1][0]=0;
ans[1][1]=1;
power(n);
ll a2=ans[0][0];
cout<<(a1-a2+mod)%mod<<endl;
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.