neeleshgoyal88's blog

By neeleshgoyal88, history, 5 weeks ago,

Actually I have solved this problem and it is passing for small variables but when i m submitting it on spoj it is giving wrong answer

I have solved it using matrix exponentiation whose equation is F(n) = 5*F(n-1)-8*F(n-2)+5*F(n-3)-F(n-4)

My code is given below :

include<bits/stdc++.h>

using namespace std;

long long mod = 1e9+7;

// Matrix Multiplication

vector<vector> multiply(vector<vector>a,vector<vector>b){ vector<vector>ans(4,vector(4)); for(long long i=0;i<4;i++){ for(long long j=0;j<4;j++){ for(long long x=0;x<4;x++){ ans[i][j] += (a[i][x]*b[x][j])%mod; ans[i][j] %= mod; } } } return ans; }

// Matrix A raised to the power N

vector<vector> power(vector<vector>&t, long long p){ if(p == 1)return t;

if(p&1){
return multiply(t,power(t,p-1));
}
vector<vector<long long>>temp = power(t,p/2);
return multiply(temp,temp);

}

void solve(){ long long n; cin>>n; vectorb = {0,1,5,17}; vectorc = {5,-8,5,-1}; vector<vector>t(4,vector(4,0)); for(long long i=0;i<4;i++){ for(long long j=0;j<4;j++){ if(i < 3){ if(i+1 == j){ t[i][j] = 1; } } else { t[i][j] = c[3-j]; } } } if(n <= 4){ cout<<b[n-1]<<"\n"; } else { t = power(t,n-1); long long ans = 0; for(long long i=0;i<4;i++){ ans += (t[0][i]*b[i])%mod; ans %= mod; } cout<<ans<<"\n"; }

}

int main(){ long long t; cin>>t; while(t--){ solve(); } }

• 0