#include<stdio.h> 
#include<stdlib.h>

typedef struct matrix {
    int rows;
    int cols;
    int **numbers;
} matrix;

void free_matrix(matrix *m) 
{
    int i;

    if(m->numbers) 
        for (i = 0; i < m->rows; i++)
            free(m->numbers[i]);
    free(m->numbers);
    free(m);
}


matrix *alloc_matrix(int rows, int cols) 
{
    int i, j;

    matrix *m = malloc(sizeof(matrix));
    if(!m) {
        return NULL;
    }
    m->rows = rows;
    m->cols = cols;

    if (!(m->numbers = calloc(rows, sizeof(int*)))) {
            free_matrix(m);
            return NULL;
            }
    for (i = 0; i < rows; i++) {
        if (!(m->numbers[i] = calloc(cols, sizeof(int)))) {
            free_matrix(m);             
            return NULL;
        }
    }
    return m;
}


/*nate matici */
void fill_matrix(matrix *m)
{
    int i, j;

    printf("Zadejte matici: \n"); 
    for (i = 0; i < m->rows; i++) {
        for (j = 0; j < m->cols; j ++) {
            scanf("%d", &m->numbers[i][j]);
        }
    }
}

/* sete matice a, b, a + b = c, vrt c, pokud nejsou matice a, b stejn vrt NULL */
matrix *add_matrix(matrix *a, matrix *b) 
{
    int i, j;
    matrix *c;

    if (!((a->rows == b->rows) || (a->cols == b->cols))) 
        return NULL;

    c = alloc_matrix(a->rows, a->cols);
    for (i = 0; i < a->rows; i++) {
        for (j = 0; j < a->cols; j++) {
            c->numbers[i][j] = a->numbers[i][j] + b->numbers[i][j];
        }
    }
    return c;
} 


void print_matrix(matrix *m)
{
    int i, j;

    for (i = 0; i < m->rows; i++) {
        for (j = 0; j < m->cols; j++) {
            printf("%d ", m->numbers[i][j]);
        }
        printf("\n");
    }
}

/* vynsob matice a a b, a * b = c, vrt c, pokud a a b maj sprvnou velikost, jinak vrt NULL */
matrix *mult_matrix(matrix *a, matrix *b) 
{
    int i, j, k;
    matrix *c;

    if (a->cols != b->rows)
        return NULL;

    c = alloc_matrix(a->rows, b->cols);
    for (i = 0; i < a->rows; i++) {
        for (j = 0; j < b->cols; j++) {
            c->numbers[i][j] = 0;
            for (k = 0; k < a->cols; k++) {
                c->numbers[i][j] += a->numbers[i][k] * b->numbers[k][j];
            }
        }
    }
    return c;
}


/* vynsob matice a, b, vsledek zape do c */
void mult_matrix2(matrix *a, matrix *b, matrix *c)
{
    int i, j, k;

    if (a->rows != b->cols)
        exit(1);

    for(i = 0; i < a->rows; i++) {
        for (j = 0; j < b->cols; j++) {
            c->numbers[i][j] = 0;
            for (k = 0; k < a->cols; k++) {
                c->numbers[i][j] += a->numbers[i][k] * b->numbers[k][j];
            }
        }
    }
}


/* do zape jednotkovou matici */
void fill1_matrix(matrix *a)
{
    int i, j;

    for (i = 0; i < a->rows; i++) {
        for (j = 0; j < a->cols; j++) {
            if (i == j)
                a->numbers[i][j] = 1;
            else 
                a->numbers[i][j] = 0;
        }
    }
}
    
    

/* umocn matici a na power = c, vrt c */
matrix *power_matrix(matrix *a, int power)
{
    int i, j, k, n = 0;
    matrix *I, *E, *c;

    if (a->rows != a->cols) 
        return NULL;

    c = alloc_matrix(a->rows, a->cols);
    I = alloc_matrix(a->rows, a->cols);
    fill1_matrix(I);
    E = alloc_matrix(a->rows, a->cols);
    while (power > 0) {
        if (power & 1) {
            for (i = 0; i < a->rows; i++) {
                for (j = 0; j < a->cols; j++) {
                    E->numbers[i][j] = I->numbers[i][j];
                }
            }
            /* pvodn matice se zkopruje do doasn I, aby se nepepisovala */
            for (i = 0; i < a->rows; i++) {
                for (j = 0; j < a->cols; j++) {
                    I->numbers[i][j] = a->numbers[i][j];
                }
            }

            /* I se umocn na 2^n */
            for (i = 0; i < n; i++) {
                mult_matrix2(I, I, c);
                for (j = 0; j < I->rows; j++) {
                    for (k = 0; k < I->cols; k++) {
                        I->numbers[j][k] = c->numbers[j][k];
                    }
                }  
            }
            mult_matrix2(I, E, c);
        }
        n++;
        power /= 2;
    }
    free_matrix(I);
    free_matrix(E);
    return c;
}

/* transponuje matici */
void transpose_matrix(matrix *a) 
{
    int i, j;
    matrix *m;

    if (a->rows == a->cols) {
        printf("A^T = \n");
        for (i = 0; i < a->rows; i++) {
            for (j = 0; j < a->cols; j++) {
                printf("%d ", a->numbers[j][i]);
            }
            printf("\n");
        }
    } else {
        m = alloc_matrix(a->cols, a->rows);
        printf("A^T = \n");
        for (i = 0; i < a->rows; i++) {
            for (j = 0; j < a->cols; j++) {
                m->numbers[j][i] = a->numbers[i][j];
            }
        }
        print_matrix(m);
        free_matrix(m);
    }
}


int main (void)
{
    int rows, cols, A, B, n;
    matrix *a, *b, *c;

    /* Zadaj se matice A a B */
    printf("Zadejte typ matice A:\n n = \n");
    scanf("%d", &rows);
    printf("m = \n");
    scanf("%d", &cols);
    if ((a = alloc_matrix(rows, cols)) == NULL) {
            printf("Chyba");
            exit(1);
            }
    fill_matrix(a);
    printf("Zadejte typ matice B:\n n = \n");
    scanf("%d", &rows);
    printf("m = \n");
    scanf("%d", &cols);
    if ((b = alloc_matrix(rows, cols)) == NULL) {
        printf("Chyba");
        exit(1);
    }
    fill_matrix(b);
    /* Stn matic */
    if ((c = add_matrix(a, b)) != NULL) {
        printf("A + B = \n");
        print_matrix(c);
        free_matrix(c);
    } else 
        printf("Chyba: matice nelze sest\n");
    /* nsoben matic */
    if ((c = mult_matrix(a, b)) != NULL) {
        printf("A * B = \n");
        print_matrix(c);
        free_matrix(c);
    } else
        printf("Chyba: matice nelze vynsobit\n");
     
    printf("Zadejte slo, na kter chcete umocnit matice A: n = \n");
    scanf("%d", &n);
    if ((c = power_matrix(a, n)) != NULL) {
        print_matrix(c);
        free_matrix(c);
    } else 
        printf("Chyba: matici nelze umocnit\n");
    transpose_matrix(a);
    free_matrix(a);
    free_matrix(b);

    return 0;
}