矩阵乘法实现斐波那契取模结果异常：排查long long与int相乘问题

核心错误点 #

你的代码在计算I = I * A_2[k]时出现了覆盖问题：调用matrix_mul(I, A_2[k], I, 2,2,2)时，函数直接将计算结果写入I的内存空间，而计算过程需要用到I的原始值，前面的元素被修改后，后续计算会错误地使用更新后的值，导致矩阵乘法结果完全偏离预期。

另外，矩阵乘法中的(long long)(A[i][x]* B[x][j])属于冗余强制转换——A和B的元素已经是long long int类型，相乘结果自然是long long，但该操作不会直接引发错误。

修复步骤 #

1. 修改矩阵乘法函数：将A和B改为const引用（避免不必要的拷贝，同时保证输入矩阵不被修改），计算结果时必须用临时空间存储，禁止直接覆盖输入矩阵。
2. 修正主函数乘法逻辑：计算I * A_2[k]时，先将结果存入临时矩阵，再赋值给I，确保始终使用I的原始值参与计算。
3. 统一输出格式：将printf("%d", 0);改为printf("%lld", 0LL);，保证输出类型匹配。

修复后的完整代码 #

#define _USE_MATH_DEFINES
#define MOD 1000000007

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

// C = A * B，使用const引用避免拷贝，保证A、B不被修改
void matrix_mul(const vector<vector<long long>>& A, const vector<vector<long long>>& B, vector<vector<long long>>& C)
{
    int n = A.size();
    int m = B.size();
    int k = B[0].size();
    // 清空C并初始化
    for (int i = 0; i < n; ++i)
        fill(C[i].begin(), C[i].end(), 0);
    
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < k; ++j)
        {
            long long sum = 0;
            for (int x = 0; x < m; ++x)
            {
                // 先累加乘积再取模，保证结果在MOD范围内
                sum = (sum + A[i][x] * B[x][j]) % MOD;
            }
            C[i][j] = sum;
        }
}

void print_matrix(const vector<vector<long long>>& A)
{
    int a = A.size();
    int b = A[0].size();
    for (int i = 0; i < a; ++i)
    {
        for (int j = 0; j < b; ++j)
            printf("%lld ", A[i][j]);
        printf("\n");
    }
}

int main()
{ 
    long long n;
    scanf("%lld", &n);
    vector<vector<long long>> A = {{1,1}, {1,0}};
    vector<vector<vector<long long>>> A_2;
    A_2.push_back(A);
    // 初始化A_2，存储A的2^0到2^63次方
    for (int i = 0; i < 64; ++i)
        A_2.push_back({{0,0}, {0,0}});
    
    // 预计算A的2^i次方
    for (int i = 0; i < 63; ++i)
        matrix_mul(A_2[i], A_2[i], A_2[i+1]);

    vector<vector<long long>> I = {{1,0}, {0,1}};
    if (n == 1)
    {
        printf("%lld\n", 0LL);
        return 0;
    }
    
    long long exponent = n - 2;
    int k = 0;
    while (exponent != 0)
    {
        if (exponent % 2 == 1)
        {
            // 用临时矩阵存储乘积，避免覆盖I的原始值
            vector<vector<long long>> temp = {{0,0}, {0,0}};
            matrix_mul(I, A_2[k], temp);
            I = temp;
        }
        exponent /= 2;
        k++;
    }
    printf("%lld\n", I[0][0]);

    return 0;
}

验证说明 #

修复后计算F_1000 % MOD会得到正确结果517691607，同时n≤45的情况依然保持正确，也能正确处理超过MOD的数值（如F_46）。

内容的提问来源于stack exchange，提问作者이형주