乘法快速幂

int fpow(int a, int n) {
    int res = 1;
    for(; n; n>>=1, a*=a) if(n&1) res*=a; 
    return res;
}

矩阵快速幂

struct matrix {
    int m[10][10], n;
    matrix(int n, int k = 0): n(n){
        for(int i = 1; i <= n; ++ i) {
            for(int j = 1; j <= n; ++ j) {
                if (i == j) m[i][j] = k;
                else m[i][j] = 0;
            }
        }
    }
    matrix operator* (matrix m2) {
        matrix res(n);
        for(int i = 1; i <= n; ++ i) {
            for(int j = 1; j <= n; ++ j) {
                for(int k = 1; k <= n; ++ k) {
                    res.m[i][j] += m[i][k] * m2.m[k][j];
                }
            }
        }
        return res;
    }
};

matrix fastpow(matrix a, int n) { // 矩阵快速幂
    matrix res(3,1);
    while(n) {
        if (n&1) res = res * a;
        n >>= 1;
        a = a * a;
    }
    return res;
}