快速幂&矩阵快速幂

· · 算法·理论

快速幂模板

P1226

注意取余和unsigned long long

(A+B)\mod m = (A\mod m + B\mod m)\mod m

(A*B)\mod m = ((A\mod m) * (B\mod m))\mod m

核心代码：

unsigned long long fastPow(unsigned long long base, unsigned long long n, unsigned long long m)
{
    unsigned long long ans = 1;
    while(n > 0)
    {
        if(n & 1)
        {
            ans *= base;
            ans %= m;
        }
        base *= base;
        base %= m;
        n >>= 1;
    }
    return ans % m;
}

矩阵快速幂模板

P3390

注意unsigned long long

主要是就是矩阵乘法和快速幂的结合，快速幂模板在上面，这里用一个结构体Matrix而不是直接用二维数组是因为这样重载运算符可以只重载这个结构体的*，不影响正常的*使用。

一分钟入门矩阵乘法规则（

#include <iostream>
#define MAXN 101
#define M 1000000007
using namespace std;

struct Matrix
{
    unsigned long long c[MAXN][MAXN];
} A, I;

unsigned long long n, k;

Matrix operator * (const Matrix &i, const Matrix &j)
{
    Matrix a;
    for(unsigned long long x = 0; x < n; x++)
        for(unsigned long long y = 0; y < n; y++) a.c[x][y] = 0;
    for(unsigned long long x = 0; x < n; x++)
        for(unsigned long long y = 0; y < n; y++)
            for(unsigned long long z = 0; z < n; z++)
            {
                a.c[x][y] += i.c[x][z] * j.c[z][y] % M;
                a.c[x][y] %= M;
            }
    return a;
}

void martrixFastPow()
{
    while(k > 0)
    {
        if(k & 1) I = I * A;
        A = A * A;
        k >>= 1;
    }
}

int main()
{
    cin >> n >> k;
    for(unsigned long long x = 0; x < n; x++)
        for(unsigned long long y = 0; y < n; y++) cin >> A.c[x][y];
    for(unsigned long long x = 0; x < n; x++) I.c[x][x] = 1;

    martrixFastPow();

    for(unsigned long long x = 0; x < n; x++)
    {
        for(unsigned long long y = 0; y < n; y++) cout << I.c[x][y] << " ";
        cout << endl;
    }
    return 0;
}