衣柜

题目描述

ZJM 有 $m$ 件衬衫，现一共有 $n$ 天。
如果 ZJM 昨天穿衬衫 $A$，今天穿衬衫 $B$，则他今天可以获得 $H[A][B]$ 快乐值。
询问 $n$ 天过后，ZJM 最多可以获得多少快乐值？

输入格式

第一行两个数 $n,m(2\le n\le 10^8, 1\le m\le 100)$，表示总天数和衬衫数量。
接下来 $m$ 行，每行 $m$ 个数，第 $i$ 行的第 $j$ 个数表示 $H[i][j](0\le H[i][j]\le 10^6)$，即昨天穿衬衫 $i$，今天穿衬衫 $j$ 可以获得的快乐值。

输出格式

输出一个数表示答案。

测试用例

输入

3 2
0 1
1 0

输出

2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//矩阵快速幂
const ll N = 101;  //方阵的大小
struct Matrix {
    ll x[N][N];
    Matrix() {
        memset(x, 0, sizeof(x));
    }
    Matrix(const Matrix &b) {
        memcpy(x, b.x, sizeof(x));
    }
    Matrix operator*(const Matrix &b) const {
        Matrix c;
        for (ll i = 0; i < N; i++)
            for (ll j = 0; j < N; j++) {
                for (ll k = 0; k < N; k++) {
                    //注意这里修改了矩阵乘法的定义，仅适用于衬衫题
                    c.x[i][j] = max(c.x[i][j], x[i][k] + b.x[k][j]);
                }
            }
        return c;
    }
};

Matrix fastpow(Matrix a, ll n) {
    //注意这里修改了矩阵快速幂的定义，仅适用于衬衫题
    Matrix res(a);
    while (n) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}

int main() {
    ll n, m, ans = 0;
    cin >> n >> m;
    Matrix a;
    for (ll i = 0; i < m; ++i)
        for (ll j = 0; j < m; ++j)
            cin >> a.x[i][j];
    a = fastpow(a, n - 2);
    for (ll i = 0; i < m; ++i)
        for (ll j = 0; j < m; ++j)
            ans = max(ans, a.x[i][j]);
    cout << ans;
    return 0;
}