快速幂与矩阵快速幂

首先介绍快速幂:

快速幂可以在常数时间内计算$$a^b$$,而朴素的算法则需要$$O(b)$$

思想:将b转换为二进制,则

$$b=1+2+4+8+……$$

$$a^b=a^{1}*a^{2}*a^{4}*….=a^{1}*(a^{1})^{2}*((a^{1})^{2})^{2}*…$$

例如:

求$$3^5$$

$$\because 5=1+4$$

$$\therefore 3^5=3^{1+4}=3^1*3^4$$

先计算$$3^1=3$$,结果乘上3 然后计算$$(3^1)^2=3^2=9$$,然后计算$$(3^2)^2=3^4=81$$,结果乘上81,最终结果为$$3*81=243$$

代码:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
using int_t = long long int;

int_t fastPower(int_t base, int_t index) {
    //结果
    int_t result = 1;
    //只要指数不为0就一直循环
    while (index) {
        //index的最低位为1,结果中应该乘上base的对应次幂
        if (index & 1) {
            result = result*base;
        }
        base = base*base;
        //index右移一位
        index >>= 1;
    }
    return result;
}

int main() {
    int_t base, index;
    while (true) {
        cin >> base>>index;
        if (base == 0 && index == 0) break;
        cout << fastPower(base, index) << endl;

    }
    return 0;
}

矩阵快速幂:

使用快速幂的思想来计算矩阵的幂

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
using int_t = unsigned long long int;
const int_t mod = (int_t) 1e9 + 7;
//Matrix的前置声明,用于下面两个函数
template 
class Matrix;
//友元函数的声明
//模板类的友元函数必须显式的写明模板
template 
ostream& operator<<(ostream & os, const Matrix & mat);
template 
istream& operator>>(istream & os, const Matrix & mat);

template 
class Matrix {
private:
    ValType* data;
    int_t row;
    int_t col;
    int_t size;
    int_t num;
public:
    //析构函数,释放内存
    ~Matrix() {
        delete[] data;
    }
    //拷贝构造函数
    Matrix(const Matrix& other) :
    row(other.row), col(other.col), size(other.size), num(other.num) {
        data = new ValType[other.num];
        memcpy(data, other.data, other.size);
    }
    //默认构造函数,动态分配内存
    Matrix(int_t r, int_t c) :
    row(r), col(c) {
        this->row = r;
        this->col = c;
        num = (row + 1)*(col + 1);
        data = new ValType[num];
        size = sizeof (ValType) * num;
        memset(data, 0, size);
    }
    //访问矩阵的某个元素
    ValType& at(int_t r, int_t c) {
        return data[c + r * col];
    }
    //重载的*运算符,矩阵无法相乘时会抛出异常
    Matrix operator*(Matrix& mat) throw (const char*) {
        if (this->col != mat.row) throw "Column number of matrix1 doesn't equals that in matrix2";
        Matrix result(this->row, mat.col);
        for (int_t i = 1; i <= this->row; i++) {
            for (int_t j = 1; j <= mat.col; j++) {
                int_t sum = 0;
                for (int_t x = 1; x <= this->col; x++) {
                    sum = (sum % mod + at(i, x) % mod * mat.at(x, j) % mod) % mod;
                }
                result.at(i, j) += sum % mod;
            }
        }
        return result;
    }

    int_t getCol() const {
        return col;
    }

    int_t getRow() const {
        return row;
    }
    //赋值构造函数
    Matrix & operator=(const Matrix & other) {
        this->col = other.col;
        this->num = other.num;
        this->row = other.row;
        this->size = other.size;
        this->data = new ValType[num];
        memcpy(data, other.data, size);
    }
    //友元,函数名后必须写<>以告诉编译器这个友元使用了模板,如果不能从参数中推断模板类型那么还必须在<>内写上模板类型
    friend ostream& operator<< <>(ostream & os, const Matrix & mat);
    friend istream& operator>> <>(istream & os, const Matrix & mat);
};
//友元函数的实现
template 
ostream & operator<<(ostream & os, Matrix & mat) {
    for (int_t i = 1; i <= mat.getRow(); i++) {
        for (int_t j = 1; j <= mat.getCol(); j++) {
            os << mat.at(i, j) % mod << " ";
        }
        os << endl;
    }
    return os;
}

template 
istream & operator>>(istream & is, Matrix & mat) {
    for (int_t i = 1; i <= mat.getRow(); i++) {
        for (int_t j = 1; j <= mat.getCol(); j++) {
            is >> mat.at(i, j);
            mat.at(i, j) %= mod;
        }
    }
    return is;
}
using MatType = Matrix;

int main() {


    int_t n, index;
    cin >> n>>index;
    MatType mat(n, n);
    cin>>mat;
    MatType result = mat;
    //普通的快速幂
    for (index--; index; index>>=1,mat = mat * mat) {
        if (index & 1) result = result * mat;
    }
    cout << result;
    return 0;
}

此外,矩阵$$A=\begin{bmatrix}
0&1 \\
1&1
\end{bmatrix}$$的n次方所得的矩阵的对角线上的元素即为斐波那契数列的第n项。