矩阵快速幂

矩阵快速幂求自幂题目

例：给定A,k,M，求对于指数为 i = (1, ....., k - 1)的A的幂次和对M取模

#include<bits/stdc++.h>

#define int long long
using namespace std;

const int N = 3;

int A, k, M;

void mul(int c[], int a[], int b[][N])
{
	int t[N] = {0};
	for ( int i = 0; i < N; i ++ ) {
		for ( int j = 0; j < N; j ++ ) {
			t[i] = (t[i] + a[j] * b[j][i] % M) % M;
		}
	}
	memcpy(c, t, sizeof t);
}

void mul(int c[][N], int a[][N], int b[][N])
{
	int t[N][N] = {0};
	for ( int i = 0; i < N; i ++ ) {
		for ( int j = 0; j < N; j ++ ) {
			for ( int k = 0; k < N; k ++ ) {
				t[i][j] = (t[i][j] + a[i][k] * a[k][j] % M) % M;
			}
		}
	}
	memcpy(c, t, sizeof t);
}

signed main()
{
	cin >> A >> k >> M;
	int f1[N] = {1, A, 1};
	int b[N][N] = {
		{0, 0, 0},
		{1, A, 1},
		{0, 0, 1}
	};
	k --;
	while (k)
	{
		if (k & 1) mul(f1, f1, b);
		mul(b, b, b);
		k >>= 1;
	}
	cout << f1[2] % M << endl;
	return 0;
}

矩阵快速幂求斐波那契数O(logn)

struct Node{
    int x[2][2];
    Node() {
        x[0][0] = x[0][1] = x[1][0] = 1;
        x[1][1] = 0;
    }
};
 
Node operator *(Node a, Node b)
{
    Node t;
    memset(t.x, 0, sizeof t.x);
    for ( int i = 0; i < 2; i ++ ) {
        for ( int j = 0; j < 2; j ++ ) {
            for ( int k = 0; k < 2; k ++ ) {
                t.x[i][j] = (t.x[i][j] + a.x[i][k] * b.x[k][j]) % mod;
            }
        }
    }
    return t;
}
 
void solve()
{
    int n;
    cin >> n;
    n --;
    Node res, m;
    while (n)
    {
        if (n & 1) res = m * res;
        n >>= 1;
        m = m * m;
    }
    cout << res.x[0][0] << endl;
}

倍增法求斐波那契数（常数比矩阵小）

#define int long long
const int mod = 1e9 + 7;

pair<int, int> fib(int n) {
    if (n == 0) return {0, 1};
    auto p = fib(n >> 1);
    int c = p.first * (2 * p.second - p.first);
    int d = p.first * p.first + p.second * p.second;
    if (n & 1)
        return {(d % mod + mod) % mod, ((c + d) % mod + mod) % mod};
    else
        return {(c % mod + mod) % mod, (d % mod + mod) % mod};
}
//fib(n)函数的返回值记为x,x.second值为第n个斐波那契数