データ構造とアルゴリズム学習ノート:高速べき乗&行列高速べき乗

1.高速べき乗時間複雑度:O(logN)

int pow(int a, int n)
{//  a^n
    int res = 1;
    while(n > 0)
    {
        if(n & 1) //n % 2 == 1
            res = res * a;
        a = a * a;
        n = n >> 1;
    }
    return res;
}

2.行列の高速べき乗ここの行列は正方行列に対してです.時間複雑度:O(logN)

//     
const int N = 4; //      
void multi(int matrix1[][N], int matrix2[][N])
{
    int res[N][N] = {0};
    for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
    for(int k = 0; k < N; k++)
        res[i][k] += matrix1[i][j] * matrix2[j][k];
    for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
        matrix1[i][j] = res[i][j];
}
int ans[N][N];
void pow(int matrix[][N], int n)
{//matrix n  
    memset(ans, 0, sizeof ans);
    for(int i = 0; i < N; i++) ans[i][i] = 1;
    while(n > 0)
    {
        if(n & 1)
            multi(ans, matrix); // ans[][] * matrix[][]
        multi(matrix, matrix);
        n = n >> 1;
    }
}

問題を解く:転送行列(「行列の等比数列」)をデリバリー式で見つけ、高速べき乗で解いてください.一般的には、f(n)とf(n-1)をF(n)とし、f(n-1)とf(n-2)をF(n-1)としてマトリックスを探します.