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;
- template
- void in(vector &a, int n, int g = 0)
- {
- for (int i = g; i < n + g; i++)
- cin >> a[i];
- }
- template
- void pvv(vector<vector>&a)
- {
- for(auto i:a)
- {
- for(auto j:i)
- cout<<j<<" ";
- cout<<endl;
- }
- }
- /*
- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- */
- 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);
- pvv(trans);
- 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()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- cout<<fixed<<setprecision(15);
- int t = 1;
- cin>>t;
- while (t--)
- {
- solver();
- }
- }
kindly help.
