11149 - Power of Matrix

[EonStrife]

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]

Anybody ?

[A1]

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]

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

[lord_burgos]

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

[mukeshtiwari]

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]

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]

Thank you
It was quite helpful but don't know why it was not giving compiler error on my pc.

[mukeshtiwari]

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]

no reply

[jurajz]

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]

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]

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

Code: Select all