## 11149 - Power of Matrix

Moderator: Board moderators

EonStrife
New poster
Posts: 4
Joined: Thu Jan 04, 2007 3:08 pm
I need help too...
I tried with test case Sanny provided, and the outputs are correct, however, I still got WA. Can anybody help me ? Thanks.

Code: Select all

``````
#include <iostream>
#include <sstream>
#include <cmath>
#include <stack>

1,		// 0 2^0
2,		// 1 2^1
4,		// 2 2^2
8,		// 3 2^3
16,		// 4 2^4
32,		// 5 2^5
64,		// 6 2^6
128,	// 7 2^7
256,	// 8 2^8
512,	// 9 2^9
1024,	// 10 2^10
2048,	// 11 2^11
4096,	// 12 2^12
8192,	// 13 2^13
16384,	// 14 2^14
32768,	// 15 2^15
65536,	// 16 2^16
131072,	// 17 2^17
262144,	// 18 2^18
524288,	// 19 2^19
};

int n;
using namespace std;

class Matrix
{
public:
Matrix();
~Matrix();

void initMatrix(bool flag);
unsigned long Cells[40][64];
//	Matrix operator+(Matrix &rhs);
//	Matrix operator*(Matrix &rhs);
};

struct Variant
{
Matrix Multiplier;
bool flag;
};

Matrix sigmaMatrix;
Matrix aMatrix;
Matrix powerMatrix[20];
Matrix globalTempMatrix[21];

Matrix::Matrix(){}
Matrix::~Matrix(){}

void Matrix::initMatrix(bool flag)
{
for(int i=0;i<n; i++)
for(int j=0;j<n; j++)
Cells[i][j]=0;

if(flag==true)
for(int i=0;i<n;i++)
Cells[i][i]=1;
}

Matrix operator %(const Matrix  &lhs, const int &rhs)
{
int j, kk;
Matrix C;
for(j=0;j<n;j++)
for(kk=0;kk<n;kk++)
C.Cells[j][kk]=lhs.Cells[j][kk]%rhs;
return C;
}

Matrix operator*(const Matrix &lhs, const Matrix &rhs)
{
int j, kk, l;
Matrix C;
C.initMatrix(false);
for(j=0;j<n;j++)
for(kk=0;kk<n;kk++)
{
for(l=0;l<n;l++)
C.Cells[j][kk]+=lhs.Cells[j][l]*rhs.Cells[l][kk];
}
return C%10;

}

Matrix operator +(const Matrix  &lhs, const Matrix &rhs)
{
int j, kk;
Matrix C;
for(j=0;j<n;j++)
for(kk=0;kk<n;kk++)
{
C.Cells[j][kk]=lhs.Cells[j][kk]+rhs.Cells[j][kk];
}
return C;
}

Matrix MatrixPower(unsigned long power)
{
Matrix temp;
unsigned long i;

temp.initMatrix(true);

for(i=0; i<20; i++)
{
{
temp = temp * powerMatrix[i];
}
}

return temp;
}

Matrix hitung(unsigned long power, unsigned long no)
{
stack<Variant>myTree;
Variant temp;
Matrix localSigma=aMatrix;
unsigned long tempPower=power;
while(tempPower!=1)
{
//		if(tempPower==1)
//		{
//			temp.Multiplier=aMatrix;
//			temp.flag=false;
//			myTree.push(temp);
//		}
if(tempPower%2==0)
{
temp.Multiplier=MatrixPower(tempPower/2);
temp.flag=true;
myTree.push(temp);
}
else
{
tempPower--;
temp.Multiplier=MatrixPower(tempPower/2);
temp.flag=false;
myTree.push(temp);
}

tempPower/=2;
}

tempPower=1;

while(!myTree.empty())
{
temp=myTree.top();
if(temp.flag)
{
localSigma=localSigma+(temp.Multiplier*localSigma);
}
else
{
}

myTree.pop();
}
return localSigma;

//
//	if(power==1)
//	{
//		return aMatrix;
//	}
//	else if(power%2==0)
//	{
//		globalTempMatrix[no]=hitung(power/2, no+1);
//		return globalTempMatrix[no]+(MatrixPower(power/2)*globalTempMatrix[no]);
//	}
//	else
//	{
//		power--;
//		globalTempMatrix[no]=hitung(power/2, no+1);
//		return globalTempMatrix[no]+(MatrixPower(power/2)*globalTempMatrix[no])+MatrixPower(power+1);
//	}

}

int main()
{
unsigned long k;
int i, j, kk;

n=1;
while(n!=0)
{

cin >> n >> k;

if(n!=0)
{
for(i=0; i<n; i++)
for(j=0; j<n; j++)
{
cin >> aMatrix.Cells[i][j];
}

powerMatrix[0]=aMatrix;

for(i=1;i<20;i++)
powerMatrix[i]=powerMatrix[i-1]*powerMatrix[i-1];

sigmaMatrix=hitung(k, 0);

for(j=0;j<n;j++)
{
for(kk=0; kk<n; kk++)
cout << sigmaMatrix.Cells[j][kk]%10 << " ";
cout << endl;
}

cout << endl;

}

}

}

``````

EonStrife
New poster
Posts: 4
Joined: Thu Jan 04, 2007 3:08 pm
Anybody ?

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Sanny wrote:Ok now it is time to post the code i think. I've spent many hours with it. This program gets WA in ~.027 seconds.

Code: Select all

``````..
..
Dummy(n);
sort(v.begin(),v.end());
rep(i,v.size()) Pow(v[i]);
sort(vs.begin(),vs.end());
rep(i,vs.size()) find_sum(vs[i]);
..
``````
maybe reassigning in map is doing trouble!! So change the part of ur code like above and get AC again

btw: u may be like to remove ur code also..

EonStrife
New poster
Posts: 4
Joined: Thu Jan 04, 2007 3:08 pm
Any help for me ? I already posted my source code (check two posts above)
Thanks.

lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:
EonStrife wrote:Any help for me ? I already posted my source code (check two posts above)
Thanks.

scanf("%d", &A[x][y]);
A[x][y] %= 10;

because 10000000 x 10000000 > int

sorry for my english

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

### Compilation Error

Could some one please help me why this code is giving compilation error. The code is working fine on my pc.

Code: Select all

``````#include<stdio.h>
#include<stdlib.h>
int n,**I,MOD=10;
int **alloc(int n)
{
int **a,i;
a=malloc(n*sizeof(int *));
for(i=0;i<n;i++)
a[i]=malloc(n*sizeof(int));
return a;
}
int **mul(int **res1,int **res2)
{
int **D,i,j,k;
D=alloc(n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
D[i][j]=0;
for( k=0;k<n;k++)
D[i][j]=(D[i][j]+(res1[i][k]*res2[k][j])%MOD)%MOD;
}
return D;
}
void cpy(int **a,int **b)
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=b[i][j];
}
void sum(int **t1,int **t2)
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
t1[i][j]=(t1[i][j]+t2[i][j])%MOD;
}
int **pow_(int** A,int n_pow)
{
if(n_pow==1)
{
int **Temp=alloc(n);
cpy(Temp,A);
return Temp;
}
int **res;
res=pow_(A,n_pow/2);
res=mul(res,res);
if(n_pow%2)
res=mul(res,A);

return res;
}
int **geom(int **A,int n_pow)
{
if(n_pow==1)
{
int **Temp=alloc(n);
cpy(Temp,A);
return Temp;
}
int **result=geom(A,n_pow/2);
int **t=pow_(A,n_pow/2);
sum(t,I);
result=mul(result,t);
if(n_pow%2)
{
int **v=pow_(A,n_pow);
sum(result,v);
}
return result;
}

int main()
{
int k,w=0,i,j;
int **A;
while(scanf("%d",&n) && n!=0)
{
scanf("%d",&k);
A=alloc(n);
I=alloc(n);
if(w)
printf("\n");
w=1;
for( i=0;i<n;i++)
{
for( j=0;j<n;j++)
{
scanf("%d",&A[i][j]);
A[i][j]=A[i][j]%10;
I[i][j]=0;

}
I[i][i]=1;
}
int** v;
v=geom(A,k);
for( i=0;i<n;i++)
for( j=0;j<n;j++)
printf("%d%c",v[i][j],(j==n-1)?'\n':' ');

}
}
``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
p.cc: In function `int** alloc(int)':
p.cc:7: error: invalid conversion from `void*' to `int**'
p.cc:9: error: invalid conversion from `void*' to `int*'

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india
Thank you
It was quite helpful but don't know why it was not giving compiler error on my pc.

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india
Could someone please tell me why judge is giving WA for this problem.Its giving all output correct for inputs given on board.If someone can point out error it will be very much thankful.

Code: Select all

``````//kindly compile with g++
#include<cstdio>
#include<cstdlib>
int n,**I,MOD=10;
int **alloc(int n)
{
int **a,i;
a=(int **)malloc(n*sizeof(int *));
for(i=0;i<n;i++)
a[i]=(int *)malloc(n*sizeof(int));
return a;
}
int **mul(int **res1,int **res2)
{
int **D,i,j,k;
D=alloc(n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
D[i][j]=0;
for( k=0;k<n;k++)
D[i][j]=(D[i][j]+(res1[i][k]*res2[k][j])%MOD)%MOD;
}
return D;
}
void cpy(int **a,int **b)
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=b[i][j];
}
void sum(int **t1,int **t2)
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
t1[i][j]=(t1[i][j]+t2[i][j])%MOD;
}
int **pow_(int** A,int n_pow)
{
if(n_pow==1)
{
int **Temp=alloc(n);
cpy(Temp,A);
return Temp;
}
int **res;
res=pow_(A,n_pow/2);
res=mul(res,res);
if(n_pow%2)
res=mul(res,A);

return res;
}
int **geom(int **A,int n_pow)
{
if(n_pow==1)
{
int **Temp=alloc(n);
cpy(Temp,A);
return Temp;
}
int **result=geom(A,n_pow/2);
int **t=pow_(A,n_pow/2);
sum(t,I);
result=mul(result,t);
if(n_pow%2)
{
int **v=pow_(A,n_pow);
sum(result,v);
}
return result;
}

int main()
{
int k,w=0,i,j;
int **A;
while(scanf("%d",&n) && n!=0)
{
scanf("%d",&k);
A=alloc(n);
I=alloc(n);
if(w)
printf("\n");
w=1;
for( i=0;i<n;i++)
{
for( j=0;j<n;j++)
{
scanf("%d",&A[i][j]);
A[i][j]=A[i][j]%10;
I[i][j]=0;

}
I[i][i]=1;
}
int** v;
v=geom(A,k);
for( i=0;i<n;i++)
for( j=0;j<n;j++)
printf("%d%c",v[i][j],(j==n-1)?'\n':' ');

}
}
``````

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia
I don't read your code in parts of computation with matrices, but i think, I found, where may be a problem. Variable w is initially set on 0, after first test case is set on 1. This cause, that before each case except the first you write a blank line. But problem description says, that there have to be blank line after each test case. But you don't write a blank line after last test case. In old system, that was PE, now missing a blank line is WA. Try to correct it, maybe this is reason of your WA

manhattan
New poster
Posts: 1
Joined: Tue Sep 29, 2009 4:23 pm

### Re: 11149 - Power of Matrix

somebody could tell me what's wrong with my program?
tks,

Code: Select all

``````#include <iomanip>
#include <iostream>

using namespace std;

const int maximo = 40;

int n, k;

struct MATRIZ {
int matriz[maximo][maximo];
MATRIZ() {
memset(matriz,0,sizeof(matriz));
}
}A, E;

void inicializa() {
memset(E.matriz,0,sizeof(E.matriz));
for(int i=0;i<maximo;i++) E.matriz[i][i] = 1;
}

for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>A.matriz[i][j];
}

MATRIZ soma(const MATRIZ &A, const MATRIZ &B) {
MATRIZ c;
for (int i=0;i<maximo;i++)
for (int j=0;j<maximo;j++)
c.matriz[i][j] = (A.matriz[i][j]+B.matriz[i][j])%10;
return c;
}

MATRIZ multiplica(const MATRIZ &A,const MATRIZ &B) {
MATRIZ C;
int tmp;
for(int i=0;i<maximo;i++)
for(int j=0;j<maximo;j++) {
tmp=0;
for(int k=0;k<maximo;k++) {
tmp += A.matriz[i][k]*B.matriz[k][j];
}
C.matriz[i][j] = tmp%10;
}
return C;
}

MATRIZ potencia(const MATRIZ B, int e){
if(e==0) {
MATRIZ I;
for(int i=0;i<maximo;i++) I.matriz[i][i]=1;
return I;
} else {
MATRIZ res = potencia(B,e/2);
res = multiplica(res,res);
if(e % 2) res = multiplica(res,B);
return res;
}
}

void imprime(const MATRIZ &B, int count) {
for(int i=0;i<count;i++) {
for(int j=0;j<count;j++) {
cout<<B.matriz[i][j]<<" ";
}
cout<<endl;
}

}

MATRIZ resolve(int k) {
if (k==0) return E;
if (k==1) return A;
if (k & 0x1){
return soma(A,multiplica(A,resolve(k-1)));
} else {
MATRIZ C = resolve(k>>1);
return soma(C, multiplica(potencia(A,k>>1),C));
}
}

int main() {
inicializa();
int controle[1][20];

bool acabou = false;
cin>>n>>k;
if(n==0) acabou = true;
while (!acabou) {
controle[0][numero] = k;
controle[1][numero] = n;
cin>>n>>k;
if(n==0) acabou = true;
numero++;
}

cout<<endl;

}

return 0;
}``````

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 11149 - Power of Matrix

The code has bug in multipling matrices . Check the mod every step..

Code: Select all

``````

``````