高精度乘法

inline string mult(string a, string b) {
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	int len1 = a.size(), len2 = b.size();
	int len = len1 + len2;
	int c[len + 10] = {};
	for(int i = 0; i < len1; i++) {
		for(int j = 0; j < len2; j++) {
			c[i + j] += (a[i] - '0') * (b[j] - '0');
		}
	}for(int i = 0; i < len - 1; i++) {
		c[i + 1] += c[i] / 10;
		c[i] %= 10;
	}while (c[len] == 0) len --;
	string ans = "";
	for(int i = len; i >= 0; i--) ans += c[i] + '0';
	if (len <= 0) ans += '0';
	return ans;
}

说到乘法，当然少不了矩阵乘法了

using matrix = vector<vector<long long> >;
matrix mult(matrix& a, matrix b) {
    int n = a.size(), m = b[0].size(), k = a[0].size();
    matrix res(n, vector<long long>(m, 0));
    for(int i = 0; i < n; i++) {
        for(int c = 0; c < k; c++) {
            for(int j = 0; j < m; j++) 
                res[i][j] = (res[i][j] + a[i][c] * b[c][j]) % mod;
        }
    }return res;
}

还有神秘的矩阵快速幂

matrix power(matrix a, long long b) {
    int n = a.size();
    matrix res(n, vector<long long>(n, 0));
    for(int i = 0; i < n; i++) res[i][i] = 1;
    auto base = a;
    while (b) {
        if (b & 1) res = mult(res, base);
        b >>= 1;
        base = mult(base, base);
    }return res;
}

高精度阶乘

inline string fact(int n) {
	string ans = "1";
	for(int i = 1; i <= n; i++) ans = mult(ans, to_string(i));
	return ans;
}

高精度次幂（普通版）

string slowPow(string a, int b) {
    if (b == 0) return "1";
    string res = "1";
    while (b --) {
        res = mult(res, a);
    }return res;
}

高精度快速幂

快速幂（迭代版）

string fastPow(string a, int b) {
    string res = "1";
    while (b > 0) {
        if (b & 1) {
            res = mult(res, a);
        }a = mult(a, a);
        b >>= 1;
    }return res;
}

快速幂（递归版）

string fastPow(string a, int b) {
    if (b == 0) return "1";
    if (b == 1) return a;

    if (!(b & 1)) {
        string t = fastPow(a, b >> 1);
        return mult(t, t);
    }else {
        return mult(a, fastPow(a, b - 1));
    }
}

对比