__sach__in__'s blog

By __sach__in__, history, 3 months ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it