ACM template

describe

Answer key

Template problem, matrix fast power, but blue bridge does not allow to bring template, or their own hand to play it!

In fact, the data range is so small, ordinary matrix multiplication by M−1 times on the line, there is no need to use the matrix fast power, not only there is no improvement in efficiency, maybe also slower, but I like to use the matrix fast power……

code

#include <cstdio>
#include <algorithm>
#include <iostream>

using namespace std;

const int MAXN = 33;

int n;

struct mat
{
    int m[MAXN][MAXN];
} unit;

mat operator * (mat a, mat b)
{
    mat ret;
    int x;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            x = 0;
            for (int k = 0; k < n; k++) { x += a.m[i][k] * b.m[k][j]; } ret.m[i][j] = x; }}return ret;
}

void init_unit(a)
{
    for (int i = 0; i < MAXN; i++)
    {
        unit.m[i][i] = 1; }}mat pow_mat(mat a, int n)
{
    mat ret = unit;
    while (n)
    {
        if (n & 1)
        {
            ret = ret * a;
        }
        n >>= 1;
        a = a * a;
    }

    return ret;
}

int main(a)
{
    int x;
    init_unit(a);while (cin >> n >> x)
    {
        mat a;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> a.m[i][j];
            }
        }
        a = pow_mat(a, x);  // a to the x

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (j + 1 == n)
                {
                    cout << a.m[i][j] << endl;
                }
                else
                {
                    cout << a.m[i][j] << ' '; }}}}return 0;
}
Copy the code

reference

Matrix Related