11149 - Power of Matrix

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Post by EonStrife » Sun Jan 14, 2007 12:35 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>
 
const long binaryMask[20] = {
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;
	Matrix Adder;
	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++)
	{
		if(power&binaryMask[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.Adder=MatrixPower(tempPower+1);
			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
		{
			localSigma=localSigma+(temp.Multiplier*localSigma)+temp.Adder;
		}

		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

Post by EonStrife » Wed Jan 17, 2007 1:57 am

Anybody ?

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Fri Jan 19, 2007 1:05 am

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

Post by EonStrife » Tue Feb 13, 2007 1:54 am

Any help for me ? I already posted my source code (check two posts above)
Thanks.

User avatar
lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

Post by lord_burgos » Thu Feb 15, 2007 1:06 am

EonStrife wrote:Any help for me ? I already posted my source code (check two posts above)
Thanks.
after read get of mod

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

because 10000000 x 10000000 > int


sorry for my english :cry:

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

Compilation Error

Post by mukeshtiwari » Sat Jan 19, 2008 9:15 pm

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:

Post by mf » Sun Jan 20, 2008 1:14 am

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

Post by mukeshtiwari » Sun Jan 20, 2008 8:17 am

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

Post by mukeshtiwari » Tue Jan 22, 2008 9:11 am

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

Post by mukeshtiwari » Sat Jan 26, 2008 12:19 pm

no reply :(

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

Post by jurajz » Mon Mar 03, 2008 12:37 am

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 :D

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

Re: 11149 - Power of Matrix

Post by manhattan » Tue Sep 29, 2009 4:26 pm

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;
}

void entrada() {
    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];
        int numero = 0,contador=0;

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

        while(contador<numero) {
            cout<<endl;
            imprime(resolve(controle[0][contador]),controle[1][contador]);
            contador++;

        }

return 0;
}

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

Re: 11149 - Power of Matrix

Post by Repon kumar Roy » Thu Feb 27, 2014 9:37 am

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

Code: Select all




Post Reply

Return to “Volume 111 (11100-11199)”