快速幂

关键思想：对指数做拆分，对底数做倍增

本文只介绍迭代版，不介绍递归版

复杂度分析

• 时间复杂度:${O(log_2N)}$，其中$log_2N$为对N进行二进制拆分的时间复杂度。
• 空间复杂度:${O(1)}$

double版

#include <iostream>

using namespace std;

typedef long long LL;

const LL MOD = 1e9 + 7;

double fast_pow(double x, LL N) {
    double res = 1.0 % MOD;
    // x = (x % MOD + MOD) % MOD;// 防止x是负数
    for (; N; N = N >> 1) { 
        if (N & 1) {
            res = res * x % MOD; // 低位为1时贡献
        }
        x = x * x % MOD;         // 倍增
    }
    
    return res;
}

PS: 函数内只能计算非负次幂(N >= 0)，如果要正负次幂通用，可以如下调用:

double pow(double x, int n) {
    long long N = n;
    return N >= 0 ? fast_pow(x, N) : fast_pow(1.0 / x, N); 
}

long long版

#include <iostream>

using namespace std;

typedef long long LL;

const LL MOD = 1e9 + 7;

LL fast_pow(LL x, LL N) {
    LL res = 1LL % MOD;
    
    for (; N; N = N >> 1)  {
        if (N & 1) {
            res = res * x % MOD; // 低位为1时贡献
        }
        x = x * x % MOD;         // 倍增
    }
    
    return res;
}

矩阵快速幂

n * n的矩阵支持乘法且满足结合律，因此也能用快速幂。

#include <iostream>

using namespace std;

typedef long long LL;

const LL MOD  = 1e9 + 7;

// 以2*2的矩阵为例子
struct Matrix {
    LL a1, a2;
    LL b1, b2;
    
    Matrix(LL _a1, LL _a2,
           LL _b1, LL _b2) : a1(_a1), a2(_a2), b1(_b1), b2(_b2) {}
    
    // 重载乘号
    Matrix operator* (const Matrix &rhs) const{
        Matrix res((a1 * rhs.a1 + a2 * rhs.b1) % MOD,
        		   (a1 * rhs.a2 + a2 * rhs.b2) % MOD,
                   (b1 * rhs.a1 + b2 * rhs.b1) % MOD,
                   (b1 * rhs.a2 + b2 * rhs.b2) % MOD);
        return res;
	}
};

Matrix fast_pow(Matrix x, LL N) {
    Matrix res(1, 0, 0, 1); // 单位矩阵
    
    for (; N; N = N >> 1) {
        if (N & 1) {
            res = res * x; // 不能用*=，没有重载
        }
        x = x * x;         // 在*的时候已经取MOD了
    }
    
    return res;
}

int main() {
    Matrix m(0, 1, 1, 1);
    
    LL n;
    scanf("%lld", &n);
    Matrix res = fast_pow(m, n - 1);
    printf("%lld\n", (res.a1 + res.a2) % MOD);
    
    return 0;
}

练习eg:

洛谷P1962-斐波那契数列

高精度快速幂 X ^ N

https://www.bilibili.com/video/BV1R14y1e7r7/?vd_source=2100aa14287ae4387e91fc75d3371399

将高精度$*$高精度 和普通快速幂的板子结合到一起：

// O(nm)
// C = A * B, A >= 0, B >= 0
vector<int> mul(const vector<int> &A, const vector<int> &B) {
    vector<int> C(A.size() + B.size());
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < B.size(); j++) {
            C[i + j] += A[i] * B[j];
        }
    }
    int t = 0;
    for (int i = 0; i < C.size(); i++) {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

vector<int> fast_pow(vector<int> x, int N) {
	vector<int> res; res.push_back(1); // 初始1

	for (; N; N = N >> 1) {
		if (N & 1) {
			res = mul(res, x);
		}
		x = mul(x, x);         // 倍增
	}

	return res;
}

A * B

高精度正整数A * 高精度正整数B，返回乘积C

基本思想先将 A[i]*B[j] 放在 C[i+j] 上，然后过一遍 C 处理进位即可

// O(nm)
// C = A * B, A >= 0, B >= 0
vector<int> mul(const vector<int> &A, const vector<int> &B) {
    vector<int> C(A.size() + B.size());
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < B.size(); j++) {
            C[i + j] += A[i] * B[j];
        }
    }
    int t = 0;
    for (int i = 0; i < C.size(); i++) {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

时间复杂度： A * B : $O(nm)$

A * B 也可以考虑用快速傅里叶变换实现，但我不会:

https://www.luogu.com.cn/problem/P3803

https://www.bilibili.com/video/BV1gY411d7Z1/?vd_source=2100aa14287ae4387e91fc75d3371399