#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mod = 1e9+7;
void print(vector< vector > v)
{
for(int i=0;i<v.size();i++)
{
for(int j=0;j<v[i].size();j++)
{
cout<<v[i][j]<<" “;
}
cout<<endl;
}
}
vector< vector > multiply(vector< vector > A, vector< vector > B){
ll acol = A[0].size(), arow = A.size(), bcol = B[0].size(), brow = B.size();
vector< vector >fans;
vector temp;
for(ll i=0;i<arow;i++)
{
temp.clear();
for(ll j=0;j<bcol;j++)
{
ll sum = 0;
for(ll k=0;k<brow;k++)
{
sum = (sum + ((A[i][k]%mod)*(B[k][j]%mod))%mod)%mod;
}
temp.push_back(sum);
}
fans.push_back(temp);
}
return fans;
}
vector< vector > expo(vector< vector > arr, ll n)
{
if(n==1)
{
return arr;
}
vector< vector > shortans = expo(arr,n/2);
vector< vector > ans = multiply(shortans,shortans);
if(n&1) ans = multiply(ans,arr);
return ans;
}
ll fib(ll n)
{
vector< vector > arr,fib_seq;
vector v1; v1.push_back(0); v1.push_back(1); arr.push_back(v1);
v1.clear(); v1.push_back(1); v1.push_back(1); arr.push_back(v1);
v1.clear(); v1.push_back(0); fib_seq.push_back(v1); v1.clear(); v1.push_back(1); fib_seq.push_back(v1);
vector< vector > matrix = expo(arr,n-1);
/cout<<“MATRIX is : \n”;
print(matrix);
cout<<endl<<endl;
cout<<“fib _seq is: \n”;
print(fib_seq);
cout<<endl<<endl;/
vector< vector > ans = multiply(matrix,fib_seq);
//print(ans);
return ans[1][0];
}
int main () {
int t;
cin>>t;
while(t–)
{
ll n;
cin>>n;
cout<<fib(n)<<”\n";
}
return 0;
}
No output Scuccesfully submitted on codechef
There may be some back-end issue. It will be resolved ASAP.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.