P10503 - 233 Matrix 题解 - JustPureH2O的博客

您已获得最佳的阅读体验！

题目地址：P10503

假设我们有一个称为 233 矩阵。在第一行，它可能是 233、2333、23333...（表示，，...）。此外，在 233 矩阵中，我们有。现在已知，你能告诉我 233 矩阵中的吗？

发现很小、很大，于是选择使用的矩阵快速幂做法。

假设矩阵一开始存储列的信息，它看起来是这样的：

由于涉及到的计算，我们需要同时递推相关项，显然有，出现了常数，连同一起，初始矩阵就应该是如下的样子：

然后可以发现：

得出的转移矩阵：

然后让初始矩阵乘以转移矩阵的次幂即可。

#include <bits/stdc++.h>
#define N 15
#define MOD 10000007
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

int n, m;
struct Matrix {
    ll mat[N][N]{};

    Matrix() {
        memset(mat, 0, sizeof mat);
    }

    void I() {
        for (int i = 1; i <= n + 2; i++) mat[i][i] = 1;
    }
};

Matrix operator*(const Matrix &l, const Matrix &r) {
    Matrix res;
    for (int i = 1; i <= n + 2; i++) {
        for (int j = 1; j <= n + 2; j++) {
            for (int k = 1; k <= n + 2; k++) {
                res.mat[i][j] = (res.mat[i][j] + l.mat[i][k] % MOD * r.mat[k][j] % MOD) % MOD;
            }
        }
    }
    return res;
}

Matrix qpow(Matrix a, ll b) {
    Matrix res;
    res.I();
    while (b) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

void print(Matrix m) {
    for (int i = 1; i <= n + 2; i++) {
        for (int j = 1; j <= n + 2; j++) {
            cout << setw(5) << m.mat[i][j] << ' ';
        }
        cout << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    while (cin >> n >> m) {
        Matrix A, M;
        A.mat[1][1] = 1, A.mat[1][2] = 23;
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            A.mat[1][i + 2] = x;
        }
        for (int i = 1; i <= n + 2; i++) {
            for (int j = i; j <= n + 2; j++) {
                M.mat[i][j] = 1;
            }
        }
        for (int i = 2; i <= n + 2; i++) M.mat[1][i] = 3, M.mat[2][i] = 10;
        A = A * qpow(M, m);
        cout << A.mat[1][n + 2] % MOD << endl;
    }
    return 0;
}