View Code of Problem 2870

#include <stdio.h>
#include <string.h>

struct Mat{
    int n;
    int a[60][60];
};

Mat mul(Mat x, Mat y, int m){
    Mat res = x;
    memset(res.a, 0, sizeof(res.a));

    for(int i = 0; i < x.n; i++)
        for(int j = 0; j < x.n; j++)
            for(int k = 0; k < x.n; k++)
                res.a[i][j] = (res.a[i][j] + x.a[i][k] * y.a[k][j]) % m;
    return res;
}

void pow(Mat base, int n, int m){
    Mat res = base;
    memset(res.a, 0, sizeof(res.a));
    for(int i = 0; i < res.n; i++)
        res.a[i][i] = 1;

    while(n){
        if(n & 1)
            res = mul(res,base,m);
        base = mul(base,base,m);
        n >>= 1;
    }

    int t = res.n / 2;
    for(int i = 0; i < t; i++){
        for(int j = t; j < 2 * t; j++)
            printf("%d ", i + t != j ? res.a[i][j] : (res.a[i][j] + m - 1) % m );
        putchar('\n');
    }
}

int main(){
    int n, k, m;
    Mat base;

    scanf("%d%d%d", &n, &k, &m);
    memset(base.a, 0, sizeof(base.a));
    base.n = 2 * n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            scanf("%d", &base.a[i][j]);
    for(int i = n; i < 2 * n; i++)
        base.a[i - n][i] = base.a[i][i] = 1;

    pow(base, k + 1, m);

    return 0;
}

Double click to view unformatted code.


Back to problem 2870