I was trying matrix exponentiation and stuck on [this](https://www.spoj.com/problems/SPP/) problem since 2 days. Please help, i was trying to create matrix like ↵
↵
~~~~~↵
transformation mat=[↵
[1 ci c(i+1) c(i+2) ....... c(i+k-1) c(i+k)]↵
[0 1 0 0 ....... 0 0 ]↵
[0 0 1 0 ....... 0 0 ]↵
[0 0 0 0 ....... 0 0 ]↵
. . . . . . . . . .↵
. . . . . . . . . .↵
[0 0 0 0 ....... 0 1 ]↵
]↵
s=[↵
s(n)↵
a(i-1)↵
a(i-2)↵
.↵
.↵
.↵
a(i-k)↵
]↵
p=[↵
s(n-1)↵
a(i-1)↵
a(i-2)↵
.↵
.↵
.↵
a(i-k)↵
]↵
~~~~~↵
↵
↵
s=mat*p↵
relation that is get was s(n)=s(n-1)+an ,where is sum of a(n) terms s(n)↵
here was my implementation :-↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define endl "\n"↵
#define int long long↵
#define double long double↵
#define dbg(x) cout << "~~~~~" << #x << "--->" << x << endl;↵
#define sz(a) ((int)(a).size())↵
typedef vector<int> vi;↵
typedef vector<vi> vvi;↵
int mod = 1e9 + 7; ↵
vvi multiply(vvi a,vvi b)↵
{↵
int n=sz(a);↵
vvi res(n,vi(n));↵
for(int i=0;i<n;i++)↵
{↵
for(int j=0;j<n;j++)↵
{↵
for(int k=0;k<n;k++)↵
{↵
res[i][j]=(res[i][j]%mod+((a[i][j]%mod)*(b[i][j]%mod))%mod)%mod;↵
}↵
}↵
}↵
return res;↵
}↵
↵
vvi pow(vvi mat,int p)↵
{↵
if(p==1)↵
return mat;↵
if( p&1 )↵
return multiply(mat,pow(mat,p-1));↵
vvi temp=pow(mat,p/2);↵
return multiply(temp,temp);↵
}↵
↵
int compute(int n,int k,vi b,vi c)↵
{↵
if(n<=k)↵
return b[n-1];↵
↵
vvi trans(k+1,vi(k+1));↵
for(int i=0;i<k+1;i++)↵
{↵
for(int j=0;j<k+1;j++)↵
{↵
if(i==0)↵
{↵
if(j==0)↵
{↵
trans[i][j]=1;↵
}↵
else↵
{↵
trans[i][j]=c[j-1];↵
}↵
}↵
else↵
{↵
trans[i][i]=1;↵
}↵
}↵
}↵
trans=pow(trans,n-k);↵
int ans=0;↵
for(int i=1;i<k+1;i++)↵
{↵
ans=(ans%mod+((trans[0][i]%mod)*(c[i-1]%mod))%mod)%mod;↵
}↵
return ans;↵
} ↵
void solver() {↵
int k;cin>>k;↵
vi b(k);↵
in(b,k); ↵
vi c(k);↵
in(c,k);↵
int m,n,p;cin>>m>>n>>p;↵
mod=p;↵
cout<<compute(n,k,b,c)-compute(m-1,k,b,c)<<endl;↵
}↵
signed main()↵
{ ↵
int t = 1;↵
cin>>t;↵
while (t--)↵
{↵
solver();↵
}↵
}↵
~~~~~↵
↵
↵
↵
kindly help.↵
↵
~~~~~↵
transformation mat=[↵
[1 ci c(i+1) c(i+2) ....... c(i+k-1) c(i+k)]↵
[0 1 0 0 ....... 0 0 ]↵
[0 0 1 0 ....... 0 0 ]↵
[0 0 0 0 ....... 0 0 ]↵
. . . . . . . . . .↵
. . . . . . . . . .↵
[0 0 0 0 ....... 0 1 ]↵
]↵
s=[↵
s(n)↵
a(i-1)↵
a(i-2)↵
.↵
.↵
.↵
a(i-k)↵
]↵
p=[↵
s(n-1)↵
a(i-1)↵
a(i-2)↵
.↵
.↵
.↵
a(i-k)↵
]↵
~~~~~↵
↵
↵
s=mat*p↵
relation that is get was s(n)=s(n-1)+an ,where is sum of a(n) terms s(n)↵
here was my implementation :-↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define endl "\n"↵
#define int long long↵
#define double long double↵
#define dbg(x) cout << "~~~~~" << #x << "--->" << x << endl;↵
#define sz(a) ((int)(a).size())↵
typedef vector<int> vi;↵
typedef vector<vi> vvi;↵
int mod = 1e9 + 7; ↵
vvi multiply(vvi a,vvi b)↵
{↵
int n=sz(a);↵
vvi res(n,vi(n));↵
for(int i=0;i<n;i++)↵
{↵
for(int j=0;j<n;j++)↵
{↵
for(int k=0;k<n;k++)↵
{↵
res[i][j]=(res[i][j]%mod+((a[i][j]%mod)*(b[i][j]%mod))%mod)%mod;↵
}↵
}↵
}↵
return res;↵
}↵
↵
vvi pow(vvi mat,int p)↵
{↵
if(p==1)↵
return mat;↵
if( p&1 )↵
return multiply(mat,pow(mat,p-1));↵
vvi temp=pow(mat,p/2);↵
return multiply(temp,temp);↵
}↵
↵
int compute(int n,int k,vi b,vi c)↵
{↵
if(n<=k)↵
return b[n-1];↵
↵
vvi trans(k+1,vi(k+1));↵
for(int i=0;i<k+1;i++)↵
{↵
for(int j=0;j<k+1;j++)↵
{↵
if(i==0)↵
{↵
if(j==0)↵
{↵
trans[i][j]=1;↵
}↵
else↵
{↵
trans[i][j]=c[j-1];↵
}↵
}↵
else↵
{↵
trans[i][i]=1;↵
}↵
}↵
}↵
trans=pow(trans,n-k);↵
int ans=0;↵
for(int i=1;i<k+1;i++)↵
{↵
ans=(ans%mod+((trans[0][i]%mod)*(c[i-1]%mod))%mod)%mod;↵
}↵
return ans;↵
} ↵
void solver() {↵
int k;cin>>k;↵
vi b(k);↵
in(b,k); ↵
vi c(k);↵
in(c,k);↵
int m,n,p;cin>>m>>n>>p;↵
mod=p;↵
cout<<compute(n,k,b,c)-compute(m-1,k,b,c)<<endl;↵
}↵
signed main()↵
{ ↵
int t = 1;↵
cin>>t;↵
while (t--)↵
{↵
solver();↵
}↵
}↵
~~~~~↵
↵
↵
↵
kindly help.↵
