问题描述

矮人种植了一种有趣的三角形植物，初始时其尖端朝上。这种植物的繁殖规律如下：经过一年，一个尖端朝上的三角形会分裂成四个小三角形，其中三个尖端朝上，一个尖端朝下。随后每年，每个三角形都会再次分裂成四个，其中三个方向与母体相同，一个方向相反。下图展示了这一过程。

给定年数 n（0 ≤ n ≤ 10¹⁸），需要计算 n 年后尖端朝上的三角形总数，结果对 1000000007 (10⁹ + 7) 取模。

输入输出示例

输入：

1

输出：

3

输入：

2

输出：

10

解题思路

定义状态向量 f[0] 表示朝上的三角形数量，f[1] 表示朝下的三角形数量。通过观察 n=1,2,3 的演化规律，可推导出转移矩阵。

设转移矩阵为：

| 3  1 |
| 1  3 |

该矩阵的含义是：每个朝上的三角形会生成 3 个朝上、1 个朝下；每个朝下的三角形会生成 1 个朝上、3 个朝下。

代码实现

#include <cstring>
#include <iostream>
using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;

ll years;
int state[2], matrix[2][2];

void multiplyState(int state[2], int mat[2][2]) {
    int temp[2] = {0};
    for (int j = 0; j < 2; ++j) {
        for (int i = 0; i < 2; ++i) {
            temp[j] = (temp[j] + (ll)state[i] * mat[i][j]) % MOD;
        }
    }
    memcpy(state, temp, sizeof(temp));
}

void multiplyMatrix(int a[2][2]) {
    int result[2][2] = {{0}};
    for (int i = 0; i < 2; ++i) {
        for (int k = 0; k < 2; ++k) {
            if (a[i][k] == 0) continue;
            for (int j = 0; j < 2; ++j) {
                result[i][j] = (result[i][j] + (ll)a[i][k] * a[k][j]) % MOD;
            }
        }
    }
    memcpy(a, result, sizeof(result));
}

int main() {
    while (cin >> years) {
        state[0] = 1;
        state[1] = 0;
        matrix[0][0] = 3; matrix[0][1] = 1;
        matrix[1][0] = 1; matrix[1][1] = 3;
        while (years > 0) {
            if (years & 1) {
                multiplyState(state, matrix);
            }
            multiplyMatrix(matrix);
            years >>= 1;
        }
        cout << (state[0] % MOD) << endl;
    }
    return 0;
}

算法说明

本解法采用矩阵快速幂技术，将递推关系转化为矩阵乘法。初始状态为 (1,0)，表示开始时只有一个朝上的三角形。通过快速幂计算转移矩阵的 n 次幂，并与初始状态相乘，最终得到 n 年后的朝上三角形数量。时间复杂度为 O(log n)，能够处理 n 高达 10¹⁸ 的输入。