This is the question : https://www.spoj.com/problems/SPP/
Here is my code:
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define ll long long
ll k;
ll mod;
vector< ll > b,c;
vector<vector<ll>> multiply(vector<vector<ll>>A, vector<vector<ll>>B){
vector<vector<ll>> C(k+2,vector<ll>(k+2));
for(ll i = 1; i<=k+1; i++){
for(ll j = 1; j<=k+1; j++){
for(ll x = 1; x<=k+1; x++){
C[i][j]=(C[i][j] + (A[i][x]*B[x][j])%mod)%mod;
}
}
}
return C;
}
vector<vector<ll>> power(vector<vector<ll>> A, ll p){
if(p == 1)
return A;
else if(p&1){
return multiply(A,power(A,p-1));
}
else{
vector<vector<ll>>X = power(A,p/2);
return multiply(X,X);
}
}
ll compute(ll n){
ll ans = 0;
//n <= k
if(n<=k)
{
for(ll i = 0; i<n; i++){
ans=(ans + b[i])%mod;
}
return ans%mod;
}
//Generate Sk
for(ll i = 0; i<k; i++){
ans=ans + b[i];
}
//creating F1 matrix
vector<ll> F(k+2);
for(ll i = 2; i<=k+1; i++){
F[i] = b[i-2];
}
F[1] = ans;
//now create transformation matrix
vector<vector<ll>>T(k+2,vector<ll>(k+2));
for(ll i = 1; i<=k+1; i++){
for(ll j = 1; j<=k+1; j++){
if(i==1){
if(j==1)
T[i][j] = 1;
else
T[i][j] = c[k+1-j];
}
else if(i==k+1){
if(j==1)
T[i][j] = 0;
else
T[i][j] = c[k+1-j];
}
else{
if(j=i+1)
T[i][j] = 1;
else
T[i][j] = 0;
}
}
}
// now calc T^(n-k)
T = power(T,n-k);
//now multiply T * F1 's where T's first row is needed
ll result = 0;
for(ll i = 1; i<=k+1; i++){
result = (result + (T[1][i]*F[i])%mod)%mod;
}
return result%mod;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//Sn+1 = Sn + an+1
//an+1 = c1.an + c2. an-1 + ...ck.an-k+1
ll test, n, m, num, p;
cin>>test;
while(test--){
cin>>k;
for(ll i = 1; i<=k; i++){
cin>>num;
b.push_back(num);
}
for(ll i = 1; i<=k; i++){
cin>>num;
c.push_back(num);
}
cin>>m>>n;
cin>>mod;
ll low = compute(m-1);
ll high = compute(n);
cout<<((high - low)%mod + mod)%mod<<endl;
b.clear();
c.clear();
}
return 0;
}
Thank you so much in advance.