要求用矩阵快速幂的方法，使时间复杂度为logn，请问如何递推？系数矩阵应该怎么写呢？C语言

Question

Answer 1

不要用递归，用递推。
还有计算 3^n ，数字会越界，大致代码如下

long long  PowerMod(long long  a, long long  b, int c)
{
    long long  ans = 1;
    a = a % c;
    while (b > 0) {
        if (b % 2 == 1)
            ans = (ans * a) % c;
        b = b / 2;
        a = (a * a) % c;
    }
    return ans;
}
int main()
{
    unsigned long long f1 = 2, f0 = 1;
    unsigned long long f2 = 0;
    unsigned long long zeta = 0;
    int n;
    cin >> n;
    auto x =3*long long(pow(3, 37));
    for (long long  i = 2; i <= n; i++) {
        zeta = PowerMod(3, i, 100000007);
        f2 = (3 * f1+ 2 * f0 + i*zeta)%100000007;
        f0 = f1%100000007;
        f1 = f2;
   
        
    }
    cout << f2;
}