This is how I implement matrix exponentiation [190118918](https://codeforces.net/gym/102644/submission/190118918) (in this example, for the problem [Fibonacci](https://codeforces.net/gym/102644/problem/C))↵
↵
But I encountered [this](https://www.hackerrank.com/contests/overnite2023/challenges/function-induction) problem before and got TLE after implementeding matrix exponentiation.↵
↵
My solution code was:↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
#define nl "\n"↵
#define ll long long↵
#define fo(i,n) for(i=0;i<n;i++)↵
#define fop(i,x,n) for(i=x;i<=n;i++)↵
typedef vector<int> vi;↵
typedef vector<ll> vl;↵
↵
const int mod = 1e9+7;↵
const int N = 2e5+5;↵
↵
vector<vl> mul(vector<vl> a,vector<vl> b){↵
ll n=a.size(),i,j,k;↵
vector<vl> ans(n,vl(n,0));↵
fo(i,n) fo(j,n) fo(k,n) ans[i][j]=(ans[i][j]+a[i][k]*b[k][j]%mod)%mod;↵
return ans;↵
}↵
↵
vector<vl> mpow(vector<vl> a,ll b){↵
ll i,n=a.size();↵
vector<vl> res(n,vl(n,0));↵
fo(i,n) res[i][i]=1;↵
while(b){↵
if(b&1) res=mul(res,a);↵
a=mul(a,a);↵
b>>=1;↵
}↵
return res;↵
}↵
↵
void solve(int test){↵
ll n;↵
char c;↵
cin>>n>>c;↵
if(n==3&&c=='g'){↵
cout<<4<<nl;↵
return;↵
}↵
if(n==3&&c=='f'){↵
cout<<5<<nl;↵
return;↵
}↵
if(n==4&&c=='f'){↵
cout<<11<<nl;↵
return;↵
}↵
if(n==1){↵
cout<<1<<nl;↵
return;↵
}↵
if(n==2){↵
cout<<2<<nl;↵
return;↵
}↵
vector<vl> v={{1,2,1,1,0},{1,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0}};↵
v=mpow(v,n-4);↵
vector<vl> v1={{2,0,1},{1,0,0},{0,1,0}};↵
v1=mpow(v1,n-3);↵
if(c=='f'){↵
cout<<(11*v[0][0]+5*v[0][1]+2*v[0][2]+v[0][3]+v[0][4])%mod<<nl;↵
}else{↵
cout<<(4*v1[0][0]+2*v1[0][1]+v1[0][2])%mod<<nl;↵
}↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);cout.tie(NULL);↵
int i,t=1;↵
cin>>t;↵
fo(i,t){↵
solve(i+1);↵
}↵
return 0;↵
}↵
~~~~~↵
↵
According to me, it should run in `O(QlogN)`, which should pass, but it gave TLE in almost all testcases. Please let me know why it failed↵
↵
P.S:- The recurrences after solving came out to be: ↵
f(n)=f(n-1)+2*f(n-2)+f(n-3)+f(n-4)↵
g(n)=2*g(n-1)+g(n-3)
↵
But I encountered [this](https://www.hackerrank.com/contests/overnite2023/challenges/function-induction) problem before and got TLE after implement
↵
My solution code was:↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
#define nl "\n"↵
#define ll long long↵
#define fo(i,n) for(i=0;i<n;i++)↵
#define fop(i,x,n) for(i=x;i<=n;i++)↵
typedef vector<int> vi;↵
typedef vector<ll> vl;↵
↵
const int mod = 1e9+7;↵
const int N = 2e5+5;↵
↵
vector<vl> mul(vector<vl> a,vector<vl> b){↵
ll n=a.size(),i,j,k;↵
vector<vl> ans(n,vl(n,0));↵
fo(i,n) fo(j,n) fo(k,n) ans[i][j]=(ans[i][j]+a[i][k]*b[k][j]%mod)%mod;↵
return ans;↵
}↵
↵
vector<vl> mpow(vector<vl> a,ll b){↵
ll i,n=a.size();↵
vector<vl> res(n,vl(n,0));↵
fo(i,n) res[i][i]=1;↵
while(b){↵
if(b&1) res=mul(res,a);↵
a=mul(a,a);↵
b>>=1;↵
}↵
return res;↵
}↵
↵
void solve(int test){↵
ll n;↵
char c;↵
cin>>n>>c;↵
if(n==3&&c=='g'){↵
cout<<4<<nl;↵
return;↵
}↵
if(n==3&&c=='f'){↵
cout<<5<<nl;↵
return;↵
}↵
if(n==4&&c=='f'){↵
cout<<11<<nl;↵
return;↵
}↵
if(n==1){↵
cout<<1<<nl;↵
return;↵
}↵
if(n==2){↵
cout<<2<<nl;↵
return;↵
}↵
vector<vl> v={{1,2,1,1,0},{1,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0}};↵
v=mpow(v,n-4);↵
vector<vl> v1={{2,0,1},{1,0,0},{0,1,0}};↵
v1=mpow(v1,n-3);↵
if(c=='f'){↵
cout<<(11*v[0][0]+5*v[0][1]+2*v[0][2]+v[0][3]+v[0][4])%mod<<nl;↵
}else{↵
cout<<(4*v1[0][0]+2*v1[0][1]+v1[0][2])%mod<<nl;↵
}↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);cout.tie(NULL);↵
int i,t=1;↵
cin>>t;↵
fo(i,t){↵
solve(i+1);↵
}↵
return 0;↵
}↵
~~~~~↵
↵
According to me, it should run in `O(QlogN)`, which should pass, but it gave TLE in almost all testcases. Please let me know why it failed↵
↵
P.S:- The recurrences after solving came out to be: ↵
f(n)=f(n-1)+2*f(n-2)+f(n-3)+f(n-4)↵
g(n)=2*g(n-1)+g(n-3)
