Help needed in SPP(spoj)

Revision en2, by __sach__in__, 2021-01-24 09:46:54

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 vi; typedef vector 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.

Tags #matrix exponentialtion, #help, #spoj

History

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