矩阵乘法

【算法竞赛进阶指南】0x34 矩阵乘法

前言 : 做算法提高课Floyd最后一题需要

定义矩阵加法(要求AB均为nm矩阵) $C=A\pm B\iff\forall i\in [1,n],\forall j\in [1, m],C_{i,j}=A_{i,j}+B_{i,j}$ 定义矩阵乘法(要求A为nm矩阵, B为mp矩阵, 结果C为np矩阵) $C_{i,j}=\sum_{k=1}^{m}A_{i,k}*B_{k,j}$ 满足结合律和分配律。

现考虑一种1n的矩阵F, A为nn矩阵, $F' = F*A$ $F$ 和 $F'$ 视作一维数组,按定义有 $\forall j\in [1,n],F'_{j} = \sum^{n}_{k=1} F_{k}*A_{k,j}$

模拟上式可以看出A可以作为系数建立 $F\rightarrow F'$ 的递推具体地, 在本题(Acwing205斐波那契)中 $F(n) = [Fi_{n} Fi_{n+1}]$ 我们尝试构造矩阵A使得F(n) * A = F(n + 1) 则有 $$ A = \begin{bmatrix} 0 & 1 \ 1 & 1 \end{bmatrix} $$ 那么答案显然: $F(n) = F(0) * A^{n}$ 由于矩阵乘法具有交换律,故求 $A^{n}$ 可以使用快速幂时间复杂度 $O(2^{3}logn)$

一般来说，如果一类问题具有一下特点：

可以抽象出一个长度为n的一维向量，该向量在每个单位时间发生一次变化；

变化的形式是一个线性递推（只有若干“加法”或“乘以个系数”的运算）；

该递推式在每个时间可能作用于不同的数据上，但是本身保持不变

向量变化时间（即递推的轮数）很长，但是向量长度n不大。

那么可以考虑把长度为n的一维向量命名为“状态矩阵”，把用于与“状态矩阵”相乘的A称为“转移矩阵”。若根据递推式构造出正确的转移矩阵就可以用快速幂和矩阵乘法实现了时间复杂度 $O(n^3logT)$

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 2e9 + 10, P = 1e4;

void mul(int f[2], int a[2][2]){
    int c[2];
    memset(c, 0, sizeof c);
    for(int j = 0; j < 2; j ++)
        for(int k = 0; k < 2; k ++)
            c[j] = (c[j] + f[k] * a[j][k]) % P;
    memcpy(f, c, sizeof c);
}

void selfmul(int a[2][2]){
    int c[2][2];
    memset(c, 0, sizeof c);
    for(int i = 0; i < 2; i ++)
        for(int j = 0; j < 2; j ++)
            for(int k = 0; k < 2; k ++)
                c[i][j] = (c[i][j] + a[i][k] * a[k][j]) % P;
    memcpy(a, c, sizeof c);
}

int main(){
    // freopen("fibonacci.in", "r", stdin);
    // freopen("fibonacci.out", "w", stdout);
    int n;
    while(cin >> n, ~n){
        int f[2] = {0, 1};
        int a[2][2] = {{0, 1}, {1, 1}};
        //求f(0) * A^n
        for(; n; n >>= 1){
            if (n & 1) mul(f, a);
            selfmul(a);
        }
        
        printf("%d\n", f[0]);
    }
    
    return 0;
}