#include <iostream>
#include <cmath>
#include <vector>

namespace gsk
{
	const int bitsInTypeOfData = 8 ;
}

class Matrix
{
public:
	Matrix( int arrSize ) : size( arrSize ) , trueSize( ( (size * size) / 8 ) + ((size * size) % 8 == 0 ? 0 : 1 ) )
	{
		array = new unsigned char[ trueSize ] ;

		for( int i = 0 ; i < trueSize ; i++ )
			array[i] = 0 ;

		for( int i = 0 ; i < gsk::bitsInTypeOfData ; i++ )
		{
			bitValues[i] = 1 << i ;
		}

		for( int i = 0 ; i < size * size ; i++ )
		{
			array[ ( i / gsk::bitsInTypeOfData )  ] |= rand()%2 * bitValues[ i % gsk::bitsInTypeOfData ] ;
		}
	}

	Matrix( const Matrix & matrix ) : size( matrix.size) , trueSize( matrix.trueSize )
	{
		array = new unsigned char[ trueSize ] ;

		for( int i = 0 ; i < gsk::bitsInTypeOfData ; i++ )
		{
			bitValues[i] = matrix.bitValues[i] ;
		}

		for( int i = 0 ; i < trueSize ; i++ )
			array[i] = matrix.array[i] ;


	}

	~Matrix()
	{
		delete [] array ;
	}

	Matrix operator=( const Matrix & matrix )
	{
		if( size == matrix.size )
		{
			for( int i = 0 ; i < trueSize ; i++ )
				array[i] = matrix.array[i] ;
		}

		return *this ;
	}

	bool get( int firstIndex , int secondIndex ) const
	{
		int trueIndex = ((secondIndex * size + firstIndex) / gsk::bitsInTypeOfData)  ;
		return ( array[ trueIndex ] & bitValues[ (secondIndex * size + firstIndex) % gsk::bitsInTypeOfData ] ) == bitValues[ (secondIndex * size + firstIndex) % gsk::bitsInTypeOfData ] ;
	}

	void set( int firstIndex , int secondIndex , bool value )
	{
		if( get( firstIndex , secondIndex ) != value )
		{
			int trueIndex = ((secondIndex * size + firstIndex) / gsk::bitsInTypeOfData) ;
			array[ trueIndex ] += ( value == true ? 1 : -1 ) * bitValues[ (secondIndex * size + firstIndex) % gsk::bitsInTypeOfData ];
		}
	}

	const int getSize() const
	{
		return size ;
	}

private:
	const int size ;
	const int trueSize ;
	int bitValues[gsk::bitsInTypeOfData] ;
	unsigned char * array  ;
};

Matrix matrixMultiplying( const Matrix & firstMatrix , const Matrix & secondMatrix )
{
	static long long int count = 0 ;

	Matrix resultMatrix( firstMatrix.getSize() ) ;

	unsigned char tmpArr[resultMatrix.getSize()][resultMatrix.getSize()] ;

	for( int i = 0 ; i < resultMatrix.getSize() ; i++ )
		for( int j = 0 ; j < resultMatrix.getSize() ; j++ )
		{
			resultMatrix.set( i , j  , firstMatrix.get( i ,0 ) & secondMatrix.get( 0 , j ) ) ;
			for( int k = 1 ; k < resultMatrix.getSize() ; k++ )
			{
				resultMatrix.set( i , j , (firstMatrix.get( i , k ) & secondMatrix.get( k , j ) ) | resultMatrix.get( i , j ) ) ;
				count++;
				if( resultMatrix.get( i , j ) )
					break ;
			}
		}



	return resultMatrix ;
}

Matrix matrixExponentiation( const Matrix & matrix , unsigned int grade )
{
	const unsigned int bitsInGradeNumber = static_cast<int>( log2(grade) + 1 ) ;
	Matrix resultMatrix( matrix.getSize() ) , tmpMatrix(matrix) ;
	int tmp = 1 ;
	bool wasTrueBit = false ;

	for( int i = 0 ; i < bitsInGradeNumber ; i++ )
	{

		if( grade & tmp == tmp )
		{
			if( wasTrueBit )
			{
				resultMatrix = matrixMultiplying( resultMatrix , tmpMatrix ) ;
			}
			else
			{
				resultMatrix = tmpMatrix ;
				wasTrueBit = true ;
			}
		}

		if( i < bitsInGradeNumber - 1 )
		{
			tmp = tmp << 1 ;
			tmpMatrix = matrixMultiplying( tmpMatrix , tmpMatrix ) ;
		}


	}

	return resultMatrix;
}

int main()
{
	srand( time(NULL) ) ;
	for( int i = 0 ; i < 1000 ; i++ )
	{
		Matrix matrix(110) ;
		matrix = matrixExponentiation( matrix , 110 ) ;
	}

	return 0 ;
}