记录编号	600609	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016][POJ3233]矩阵幂之和	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	4.522 s
提交时间	2025-05-08 19:02:52	内存使用	2.88 MiB

#include <cstdio>
#include <cstring>
#include <cctype>
typedef __int128 int128;
typedef long long ll;

template <typename T>
T read() {
    T sum = 0, fl = 1;
    int ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-') fl = -1;
    for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
    return sum * fl;
}

template <typename T>
void write(T x) {
    static T sta[40];
    int top = 0;
    do {
       sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48);
    putchar(' ');
}

ll n, k;
int128 mod;

struct Matrix {
    int128 a[40][40];
    void Clear() {memset(a, 0, sizeof a);}
    void Print() {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                write(a[i][j]);
            }
            printf("\n");
        }
    }
};
Matrix operator * (Matrix x, Matrix y) {
    Matrix res; res.Clear();
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= n; ++k) {
                res.a[i][j] += x.a[i][k] % mod * y.a[k][j] % mod;
                res.a[i][j] %= mod;
            }
        }
    }
    return res;
}
Matrix operator + (Matrix x, Matrix y) {
    Matrix res; res.Clear();
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            res.a[i][j] = x.a[i][j] % mod + y.a[i][j] % mod;
            res.a[i][j] %= mod;
        }
    }
    return res;
}
Matrix operator - (Matrix x, Matrix y) {
    Matrix res; res.Clear();
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            res.a[i][j] = x.a[i][j] - y.a[i][j];
            res.a[i][j] = ((res.a[i][j] % mod) + mod) % mod;
        }
    }
    return res;
}

struct Matrix2 {
    Matrix a[3][3];
    void Clear() {
        for (int i = 1; i <= 2; ++i) {
            for (int j = 1; j <= 2; ++j) {
                a[i][j].Clear();
            }
        }
    }
};
Matrix2 operator * (Matrix2 x, Matrix2 y) {
    Matrix2 res; res.Clear();
    for (int i = 1; i <= 2; ++i) {
        for (int j = 1; j <= 2; ++j) {
            for (int k = 1; k <= 2; ++k) {
                res.a[i][j] = res.a[i][j] + (x.a[i][k] * y.a[k][j]);
            }
        }
    }
    return res;
}
Matrix2 kasumi(Matrix2 x, ll y) {
    Matrix2 res = x;
    y--;
    while (y) {
        if (y & 1) res = res * x;
        y >>= 1;
        x = x * x;
    }
    return res;
}

Matrix A, E, O;
Matrix2 M;
Matrix X;

int main() {
    freopen("matrix_sum.in", "r", stdin);
    freopen("matrix_sum.out", "w", stdout);
    n = read<ll>(), k = read<ll>(), mod = read<int128>();
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            A.a[i][j] = read<int128>();
            A.a[i][j] %= mod;
        }
        E.a[i][i] = 1;
    }
    M.a[1][1] = A, M.a[1][2] = E, M.a[2][1] = O, M.a[2][2] = E;
    (kasumi(M, k + 1).a[1][2] - E).Print();
    return 0;
}