Hey guys!!
I am new to matrix exponentiation and its use in solving linear
recurrences..and have been trying to solve a problem which uses it. The
link to the problem is http://www.codechef.com/JULY12/problems/CSUMD.
I have tried understanding the code of the users who have submitted the
solution to the problem bt since m new..i am not able to get a number of
things like why most of them have taken a 3 d array with the highest
dimension size as 31 or 34..
i have tried this question through recursion and i got the right ans bt m
not getting the right ans using this technique..Here is the code i am
using..
#include<iostream>
#include<conio.h>
using namespace std;
#define mod 1000000007
class matrix
{
int a,b;
public:
int *mat;
matrix(int r,int c)
{ a=r;
b=c;
mat=new int[r*c];
}
matrix &operator^(int n);
matrix &operator*(matrix p);
}m(2,2),f(2,1);
matrix &matrix::operator^(int n)
{
if(n==1)
return m;
if(n%2==0)
{
return (m^(n/2))*(m^(n/2));
}
else
return m*(m^(n-1));
}
matrix &matrix::operator*(matrix p)
{
matrix temp(a,p.b);
for(int i=0;i<a;i++)
{
for(int j=0;j<p.b;j++)
{
int count=0;
for(int k=0;k<b;k++)
{
count+=mat[i*b+k]*p.mat[k*(p.b)+j];
}
temp.mat[i*p.b+j]=count;
}
}
return temp;
}
main()
{
int t;
cin>>t;
m.mat[0]=2;
m.mat[1]=2;
m.mat[2]=1;
m.mat[3]=0;
f.mat[0]=3;
f.mat[1]=1;
for(int i=0;i<t;i++)
{
long int n;
cin>>n;
if(n==2)
{
cout<<2<<endl;
continue;
}
if(n==1)
{
cout<<1<<endl;
continue;
}
if(n>2)
{
matrix z=m^(n-1);
matrix y=z*f;
long int ans=(y.mat[1])%mod;
cout<<ans<<endl;
}
}
getch();
}
please tell me where m i going wrong!
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/_ipm8wMIbIAJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
