### __sach__in__'s blog

By __sach__in__, history, 4 months ago, I was trying matrix exponentiation and stuck on this 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[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.  Comments (5)
 » Auto comment: topic has been updated by __sach__in__ (previous revision, new revision, compare).
 » Hm. It should be $S = \{ sum[n], a[n], \dots a[n-k+1] \}^T$ $P = \{ sum[n-1], a[n-1], \dots a[n-k] \}^T$Consequently $\begin{equation*} mat = \begin{pmatrix} 1 & c & c & \cdots & c[k-1] & c[k] \\ 0 & c & c & \cdots & c[k-1] & c[k] \\ 0 & 1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0 \end{pmatrix} \end{equation*}$
•  » » Thank you!! yea got my mistake but still i am getting wrong answer. can you tell where it went wrong? this is my code codeint k; vvi mult(vvi a,vvi b) { int n=sz(a); vvi res(n,vi(n)); rep(i,0,n) { rep(j,0,n) { rep(m,0,n) { res[i][j]=((res[i][j]%mod)+((a[i][m]%mod)*(b[m][j]%mod))%mod)%mod; } } } return res; } vvi pow(vvi a,int n) { if(n==1) return a; if(n&1) return mult(a,pow(a,n-1)); vvi t=pow(a,n/2); return mult(t,t); } int compute(int n,vi b,vi c) { if(n<=k) return b[k-1]; vvi trans(k+1,vi(k+1)); rep(i,0,k+1) { rep(j,0,k+1) { if(i==0) { if(j==0) trans[i][j]=1; else trans[i][j]=c[j-1]; } else if(i==1) { if(j!=0) trans[i][j]=c[j-1]; } else { trans[i][i-1]=1; } } } trans=pow(trans,n-k); int ans=trans%mod; rep(i,1,k+1) { ans=(ans%mod+((trans[i]%mod)*(c[i-1]%mod))%mod)%mod; } return ans; } void solver() { cin>>k; vi b(k); in(b,k); vi c(k); in(c,k); int n,m,p; cin>>m>>n>>p; mod=p; cout<<(compute(n,b,c)-compute(m-1,b,c))%mod<
•  » » » Oh, too hard to list all wrong points in you code. Some spotted errors: if(n<=k) return b[n-1]; You should sum up the values b[i] for from i=1 to i=n.  if( n <= k ) { long long sum = 0; for( int i = 1; i <= x; ++i) sum += b[i-1]; return (int) (sum % m); } Moreover the input values b[], c[] can be equal or greater than modulo:  for( int i = 1; i <= k; ++i) b[i-1] %= m, c[i-1] %= m;  for(int i=1;i
•  » » » » yes i have corrected mentioned errors. still wrong answer i think some more bugs are there :(