#include <iostream>
#include <stdint.h>
#include <stdio.h>

using namespace std;

// класс, реализующий матрицу
class Matrix
{
   public:

      // конструктор по умолчанию
      Matrix()
      : mNumRows(0)
      , mNumCols(0)
      , mArr(0)
      {
      }

      // конструктор, создающий реальную матрицу ненулевой размерности и заполняет начальным значением
      Matrix( int numRows, int numCols, double initValue )
      : mNumRows( 0 )
      , mNumCols( 0 )
      , mArr( 0 )
      {
         initArr( numRows, numCols, initValue );
      }
      
      // конструктор копии - создающий матрицу как копию матрици-источника
      Matrix( Matrix& source )
      : mNumRows( source.mNumRows )
      , mNumCols( source.mNumCols )
      , mArr( 0 )
      {
         swap( source );
      }

      // деструктор, необходим для удаления выделенного на куче двумерного массива
      ~Matrix()
      {
         resetArr();
      }

      // переопределённый оператор присваивания, необходим для корректного присваивания матриц
      Matrix& operator=( Matrix& rhs )
      {
         swap( rhs );
      }

      // возвращает число строк в матрице
      int getNumRows() { return mNumRows; };

      // возвращает число колонок в матрице
      int getNumCols() { return mNumCols; };

      // возвращает указатель на двумерный массив на куче, содержащий саму матрицу
      double** getArr() { return mArr; };

      // копирует матрицу-источник в себя
      void swap( Matrix& another );

      // создает левую диагональ, заполненную заданным значением
      void setLeftDiag( double value );

      // суммирует другую матрицу с собой
      void sum( Matrix& another );

      // возводит себя в n-ю степень
      void power( int n );

      //выполняет произведение себя и другой матрицы, метод используется в методе power
      void product( Matrix& another );

      // умножает себя на заданное значение
      void multiply( double& value );

      // выводит на консоль содержимое себя, придворенное заголовком
      void show( const char* title );

      // создает заново свой двумерный массив и заполняет заданным значеним, исп. в конструкторе
      void initArr( int numRows, int numCols, double initValue );

      // удаляет двумерный массив из кучи и обнуляет указатель, исп. в деструкторе а также в initArr
      void resetArr();

   private:

      int mNumRows;
      int mNumCols;
      double** mArr;
};

void Matrix::swap( Matrix& another )
{
   initArr( another.mNumRows, another.mNumCols, 0 );
   for( int row = 0; row < mNumRows; row++ )
   {
      for( int col = 0; col < mNumCols; col++ )
      {
         mArr[ row ][ col ] = another.mArr[ row ][ col ];
      }
   }
}

void Matrix::setLeftDiag( double value )
{
   int n = min( mNumRows, mNumCols );
   for( int i = 0; i < n; i++ )
   {
      mArr[ i ][ i ] = value;
   }
}

void Matrix::sum( Matrix& another )
{
   int numRows = min( mNumRows, another.getNumRows() );
   int numCols = min( mNumCols, another.getNumCols() );

   for( int row = 0; row < mNumRows; row++ )
   {
      for( int col = 0; col < mNumCols; col++ )
      {
         mArr[ row ][ col ] += another.mArr[ row ][ col ];
      }
   }
}

void Matrix::power( int n )
{
   for( int i = 1; i < n; i++ )
   {
      product( *this );
   }
}

void Matrix::product( Matrix& another )
{

   if ( mNumCols != another.mNumRows )
   {
      printf( "*** Matrix::product: argument matrix is not complementary, production is impossible ***\n" );
      return;
   }

   Matrix result( mNumRows, another.mNumCols, 0 ); 

   for( int rowResult = 0; rowResult < result.mNumRows; rowResult++ )
   {
      for( int colResult = 0; colResult < result.mNumCols; colResult++ )
      {
         result.mArr[ rowResult ][ colResult ] = 0;
         for( int col = 0; col < mNumCols; col++ )
         {

            result.mArr[ rowResult ][ colResult ] +=
               ( mArr[ rowResult ][ col ] * another.mArr[ col ][ colResult ] );
         }
      }
   }

   swap( result );
} 

void Matrix::multiply( double& value )
{
   for( int row = 0; row < mNumRows; row++ )
   {
      for( int col = 0; col < mNumCols; col++ )
      {
         mArr[ row ][ col ] *= value;
      }
   }
}

void Matrix::show( const char* title )
{
   printf("%s:\n", title);

   for( int row = 0; row < mNumRows; row++ )
   {
      for( int col = 0; col < mNumCols; col++ )
      {
         printf("%10.04lf ", mArr[ row ][ col ] );
      }
      printf("\n");
   }
}

void Matrix::initArr( int numRows, int numCols, double initValue )
{
   resetArr();
   mNumRows = numRows;
   mNumCols = numCols;
   mArr = new double*[ mNumRows ]; // создает массив указателей на подмассивы колонок
   for( int row = 0; row < mNumRows; row++ )
   {
      mArr[ row ] = new double[ mNumCols ]; // создает подмассив колонок для данной строки
      for( int col = 0; col < mNumCols; col++ ) // заполняет подмассив колонок заданным значениям
      {
         mArr[ row ][ col ] = initValue;
      }
   }
}

void Matrix::resetArr()
{
   if ( mArr!= 0 )
   {
      for( int row = 0; row < mNumRows; row++ )
      {
         delete[] mArr[ row ];
      }
      delete [] mArr;
      mArr = 0;
   }
}

//==============================================================================

// ввыд с консоли какого либо целого числа
static int inputNumber( const char *title )
{
   int n = 0;

   printf("input %s:\n", title);

   if ( scanf("%d", &n ) <= 0 )
   {
      printf("error input of %s\n",title);
   }
   else
   if ( n <= 0 )
   {
      printf("wrong %s value, must be positive\n", title);
   }

   return n;
}

// ввод с консоли содержимого какой либо матрицы
static bool inputMatrixData( const char *title, Matrix& x )
{
   printf("input %dx%d %s:\n", x.getNumRows(), x.getNumCols(), title );

   for( int row = 0; row < x.getNumRows(); row++ )
   {
      for( int col = 0; col < x.getNumCols(); col++ )
      {
         double val = 0;
         if ( scanf("%lf", &val ) <= 0 )
         {
            printf("error input of %s\n",title);
            return false;
         }
         x.getArr()[ row ][ col ] = val;

      }
   }
   return true;
}

//==============================================================================

int main()
{
   int numIter = inputNumber( "Number of iterations 'n'" );
   int sizeA   = inputNumber( "matrix size 'm'" );

   if ( numIter <= 0 || sizeA <= 0 )
   {
      return 0;
   }

   Matrix mxP( 1, numIter, 0 ); // для хранения p_0, P_1, ... P_n
   if ( ! inputMatrixData( "P matrix values", mxP ) )
   {
      return 0;
   }

   Matrix mxA( sizeA, sizeA, 0 );
   if ( ! inputMatrixData( "A matrix values", mxA ) )
   {
      return 0;
   }

   Matrix mxE( sizeA, sizeA, 0 );
   mxE.setLeftDiag( 1 );

   // печатаем исходные данные перед вычислением
   mxE.show("============= matrix E ==============");
   mxP.show("============= matrix P ==============");
   mxA.show("============= matrix A ==============");

   Matrix s; // это будет общая сумма полинома

   s.swap( mxE );

   s.multiply( mxP.getArr()[0][0] ); // создает P_0*E, как начальное значение суммирования

   // главный цикл суммирования полинома
   for( int i = 1; i < numIter; i++ )
   {
    
      Matrix x;  // это будет временная матрица для вычисления одного слагаемого полинома (pow(A,i)*P_i*E)
      x.swap( mxA ); // копируем содержимое матрицы A

      x.power( i );  // возводим x в степень i, т.е. pow(A,i)

      x.multiply( mxP.getArr()[0][i] ); // умножаем x на коэфф. p_i , т.е. полуйчаем результат одного слогаемого (pow(A,i)*P_i)

      s.sum( x ); // накапливаем сумму полинома

   }

   s.show("============= result: ==============");// печатаем результат вычисления полинома
   
   return 0;
}