__sach__in__'s blog

By __sach__in__, history, 4 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.

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by __sach__in__ (previous revision, new revision, compare).

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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[1] & c[2] & \cdots & c[k-1] & c[k] \\ 0 & c[1] & c[2] & \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*} $$$
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you!! yea got my mistake but still i am getting wrong answer. can you tell where it went wrong? this is my code

    code
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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<k+1;i++) { ans=(ans%mod+((trans[0][i]%mod)*(c[i-1]%mod))%mod)%mod;

      Why did you multiply on c[i] (i.e. coefficients) instead of b[i] (i.e. initial values)? Why did you start the cycle from 1 and not from zero (thus you got the a[n] value, but not the sum of values)?

      cout<<compute(n,k,b,c)-compute(m-1,k,b,c)<<endl;

      This difference can be negative.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes i have corrected mentioned errors. still wrong answer i think some more bugs are there :(