Быстрое возведение в степень

Базовая реализация

long long binPow(long long x, long long p, long long mod) {
    if (!p)
        return 1 % mod;
    if (p % 2)
        return binPow(x, p - 1, mod) * x % mod;
    long long r = binPow(x, p / 2, mod);
    return r * r % mod;
}

Вычисление степеней, превышающих размер long long

Если x и mod взаимно просты, то binPow(x, p, mod) == binPow(x, p % phi(mod), mod), где phi — функция Эйлера.

Если x и mod не взаимно просты, но p ≥ log₂(mod), то binPow(x, p, mod) == binPow(x, p % phi(mod) + phi(mod), mod).

long long phi(long long n) {
    long long res = n;
    for (long long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            while (n % d == 0)
                n /= d;
            res -= res / d;
        }
    }
    if (n > 1)
        res -= res / n;
    return res;
}

Возведение в степень матриц

const long long MOD = 1e9 + 7;

using Matrix = vector<vector<long long>>;

Matrix identityMatrix(int size) {
    Matrix res(size, vector<long long>(size));
    for (int i = 0; i < res.size(); i++)
        res[i][i] = 1;
    return res;
}

Matrix operator * (const Matrix &a, const Matrix &b) {
    Matrix res(a.size(), vector<long long>(b[0].size()));
    for (int y = 0; y < res.size(); y++)
        for (int x = 0; x < res[0].size(); x++)
            for (int i = 0; i < a[0].size(); i++)
                res[y][x] = (res[y][x] + a[y][i] * b[i][x] % MOD) % MOD;
    return res;
}

Matrix pow(const Matrix &m, long long p) {
    if (!p)
        return identityMatrix(m.size());
    if (p % 2)
        return pow(m, p - 1) * m;
    Matrix r = pow(m, p / 2);
    return r * r;
}

Ссылки

• E-maxx — Бинарное возведение в степень
• cp-algorithms.com — Binary Exponentiation
• cp-algorithms.com — Euler's totient function application in Euler's theorem
• algorithmica.org — Теория чисел
• Codeforces — Cool tricks using Matrix Exponential
• Habr — Используем быстрое возведение матриц в степень для написания очень быстрого интерпретатора простого языка программирования
• Habr — Автоматическая оптимизация алгоритмов с помощью быстрого возведения матриц в степень