题目描述

大豆有无限多个尺寸为 \(3 \times 1 \times 1\) 的积木，他想搭一座宽 \(3\)、深 \(1\)、高 \(n\) 的塔。积木可以横放，也可以竖放。求不同的搭建方案数对 \(10^9+7\) 取模的结果。

其中 \(0 \le n \le 2^{64}-1\)。

思路分析

由于塔的深度固定为 \(1\)，问题等价于：在一个 \(3 \times n\) 的二维网格中，用 \(3 \times 1\) 和 \(1 \times 3\) 的矩形进行完美覆盖，求方案数。

考虑最顶层的 \(1\) 个单位高度是如何被填满的：

• 情况一：横放一块积木
  占据 \(3 \times 1\) 的空间，剩余高度为 \(n-1\)，方案数为 \(f[n-1]\)。

• 情况二：竖放三块积木
  三块并排，占据 \(3 \times 3\) 的空间，剩余高度为 \(n-3\)，方案数为 \(f[n-3]\)。

因此得到递推式：

\[ f[i] = f[i-1] + f[i-3] \]

边界条件：

\[ f[0] = 1,\quad f[1] = 1,\quad f[2] = 1 \]

例如：
- \(f[3] = f[2] + f[0] = 2\)
- \(f[4] = f[3] + f[1] = 3\)
- \(f[10] = 28\)，与题目样例一致。

为什么需要矩阵快速幂

\(n\) 最大可达 \(2^{64}-1\)，直接线性递推 \(O(n)\) 会超时。观察到递推式是线性的，且阶数为 \(3\)，可以用矩阵快速幂在 \(O(3^3 \log n)\) 时间内求出 \(f[n]\)。

矩阵构造

设状态向量：

\[ \begin{pmatrix} f[i] \\ f[i-1] \\ f[i-2] \end{pmatrix} \]

则：

\[ \begin{pmatrix} f[i+1] \\ f[i] \\ f[i-1] \end{pmatrix} = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} f[i] \\ f[i-1] \\ f[i-2] \end{pmatrix} \]

令转移矩阵为 \(M\)，则：

\[ \begin{pmatrix} f[n] \\ f[n-1] \\ f[n-2] \end{pmatrix} = M^{\,n-2} \begin{pmatrix} f[2] \\ f[1] \\ f[0] \end{pmatrix} = M^{\,n-2} \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} \quad (n \ge 2) \]

对于 \(n = 0, 1, 2\)，直接输出 \(1\)。

参考代码（C++）

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007LL;

struct Mat {
    long long a[3][3];
    Mat() { memset(a, 0, sizeof(a)); }

    static Mat identity() {
        Mat I;
        for (int i = 0; i < 3; ++i) I.a[i][i] = 1;
        return I;
    }
};

Mat mul(const Mat& A, const Mat& B) {
    Mat C;
    for (int i = 0; i < 3; ++i)
        for (int k = 0; k < 3; ++k) {
            if (A.a[i][k] == 0) continue;
            for (int j = 0; j < 3; ++j) {
                C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % MOD;
            }
        }
    return C;
}

Mat mpow(Mat base, unsigned long long exp) {
    Mat res = Mat::identity();
    while (exp) {
        if (exp & 1) res = mul(res, base);
        base = mul(base, base);
        exp >>= 1;
    }
    return res;
}

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

    unsigned long long n;
    cin >> n;

    if (n == 0 || n == 1 || n == 2) {
        cout << 1 % MOD << '\n';
        return 0;
    }

    // 转移矩阵 M
    Mat M;
    M.a[0][0] = 1; M.a[0][2] = 1;
    M.a[1][0] = 1;
    M.a[2][1] = 1;

    Mat P = mpow(M, n - 2);

    // 初始向量 [f[2], f[1], f[0]]^T = [1, 1, 1]^T
    long long f2 = 1, f1 = 1, f0 = 1;
    long long fn = (P.a[0][0] * f2 + P.a[0][1] * f1 + P.a[0][2] * f0) % MOD;

    cout << fn << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：\(O(3^3 \log n) = O(\log n)\)
• 空间复杂度：\(O(1)\)

坑点提示

1. 取模时机：矩阵乘法中每一步加法和乘法后都要对 \(10^9+7\) 取模，否则 long long 会溢出。
2. 输入范围：\(n\) 最大为 \(2^{64}-1\)，必须用 unsigned long long 读取，使用 cin 或 scanf("%llu", &n)。
3. 边界处理：\(n=0,1,2\) 时直接输出 \(1\)，不要忘记。
4. 矩阵乘法顺序：矩阵乘法不满足交换律，计算 \(M^{\,n-2}\) 时要注意左乘右乘的顺序，但快速幂中 res = mul(res, base) 和 base = mul(base, base) 是标准的。