题解 | #洋灰三角#

• 考点：递推式计算 矩阵快速幂

• 注意点：负数的模应该先加上MOD再模

设s(n)为n个格子铺满需要多少洋灰三角。根据题意，可以得出如下递推式：

因此可以构造出：

以此递推即可得到：

因此问题就转化为求一个三阶矩阵的高次幂，与纯数的快速幂类似，只是将数的乘法改为矩阵乘法即可。(吐槽：牛客MD编辑器真难用，基本的Latex公式都表示不出来)

//
// Created by Zed on 2024/2/10.
//


/*
 * 链接：https://ac.nowcoder.com/acm/problem/17510
来源：牛客网

题目描述
    洋灰是一种建筑材料，常用来筑桥搭建高层建筑，又称，水泥、混凝土。
    WHZ有很多铸造成三角形的洋灰块，他想把这些洋灰三角按照一定的规律放到摆成一排的n个格子里，其中第i个格子放入的洋灰三角数量是前一个格子的k倍再多p个，特殊地，第一个格子里放1个。
    WHZ想知道把这n个格子铺满需要多少洋灰三角。
#include <iostream>

using namespace std;
const long long MAXN = 10;
const long long MOD = 1e9 + 7;//模数
struct Matrix {
    long long a[MAXN][MAXN];//从下标0开始使用
    long long c, r;//r行c列

    Matrix() : a(), c(), r() {}

    Matrix(const long long *aa, long long rr, long long cc) : a(), c(), r() {
        c = cc;
        r = rr;
        for (long long i = 0; i < r; ++i) {
            for (long long j = 0; j < c; ++j) {
                a[i][j] = *(aa + i * cc + j);
            }
        }
    }

    void multi(Matrix m, long long mod) {
        Matrix matrix;
        for (long long i = 0; i < r; ++i) {
            for (long long j = 0; j < m.c; ++j) {
                matrix.a[i][j] = 0;
                for (long long k = 0; k < c; ++k) {
                    matrix.a[i][j] = (matrix.a[i][j] + (a[i][k] * m.a[k][j]+mod) % mod+mod) % mod;
                }
            }
        }
        c = m.c;
        for (long long i = 0; i < r; ++i) {
            for (long long j = 0; j < c; ++j) {
                a[i][j] = matrix.a[i][j];
            }
        }
    }

    void output() {
        for (long long i = 0; i < r; ++i) {
            for (long long j = 0; j < c; ++j) {
                cout << a[i][j] << " ";
            }
            cout << endl;
        }
    }

    static Matrix fastPow(Matrix base, long long r, long long mod) {//矩阵快速幂
        if (r == 0) {
            return base;
        }
        Matrix ans;
        ans.c = base.c;
        ans.r = base.r;
        for (long long i = 0; i < ans.c; ++i) {
            ans.a[i][i] = 1;
        }
        while (r) {
            if (r & 1) {
                ans.multi(base, mod);
            }
            base.multi(base, mod);
            r >>= 1;
        }
        return ans;
    }
};

signed main() {//
    long long n, k, p;
    cin >> n >> k >> p;
    long long tmp[][3] = {{k + 1, -k, 1},
                          {1,     0,  0},
                          {0,     0,  1}};
    Matrix base((long long *) tmp, 3, 3);
    base = Matrix::fastPow(base, n - 1, MOD);
    cout << (long long)(base.a[0][0] + (base.a[0][2] * p) % MOD) % MOD << endl;//s0=0 s1=1
    return 0;
}