Help needed in SPP(spoj)

Revision en4, by __sach__in__, 2021-01-24 09:55:36

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[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.

History

Revisions

Rev. Lang. By When Δ Comment
en4 __sach__in__ 2021-01-24 09:55:36 0 (published)
en3 __sach__in__ 2021-01-24 09:50:28 38
en2 __sach__in__ 2021-01-24 09:46:54 865 (saved to drafts)
en1 __sach__in__ 2021-01-24 09:43:23 3294 Initial revision (published)