矩阵乘法

A = a*b
B = b*c
A x B = a*c
  
for(int i=1;i<=a;i++){
  	for(int j=1;j<=c;j++){
        for(int k=1;k<=b;k++){
            C[i][j]+=A[i][k]*B[k][j];
        }
    }
}

矩阵快速幂求斐波那契

题意

求斐波那契第i项

思路

利用矩阵运算的性质将通项公式变成幂次形式，然后用平方倍增（快速幂）的方法求解第 n 项。

首先我们定义向量

$X_{n}=\left[\begin{array}{ll} a_{n} & a_{n-1} \end{array}\right] \text {, 边界 : } X_{1}=\left[\begin{array}{ll} a_{1} & a_{0} \end{array}\right]$

然后我们可以找出矩阵:

$A=\left[\begin{array}{ll} 1 & 1 \\ 1 & 0 \end{array}\right]$

则有:

$X_{n}=X_{n-1} \times A$

所以：

$X_{n}=X_{1} \times A^{n-1}$

由于矩阵具有结合律, 所以我们可以先求出 $A^{n-1} \% P$, 然后再用 $X_{1}$ 左乘, 即可求出 $X_{n}$, 向量 $X_{n}$ 的第一个元素就是 $a_{n}$ 。

斐波那契前 n 项和

题意

思路

代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
LL A[3][3]={1,1,1,
            1,0,0,
            0,0,1};
LL B[3][3]={1,0,0,
            0,1,0,
            0,0,1};
LL n,m;
LL F[3]={1,1,1};

void mul(LL a[3][3],LL b[3][3]){
    LL temp[3][3];
    memset(temp,0,sizeof temp);
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                temp[i][j]=(temp[i][j]+a[i][k]*b[k][j])%m;
            }
        }
    }
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            a[i][j] = temp[i][j];
}

int main()
{
    cin>>n>>m;
    n--;
    while(n){
        if(n&1) mul(B,A);
        mul(A,A);
        n>>=1;
    }
    cout<<(B[0][2]+B[1][2]+B[2][2])%m;
    return 0;
}

总结

先列出 Fi 和 Fi-1 再直接写出A。有点动态规划的意思。

佳佳的斐波那契

题意

用 $T(n)=\left(F_{1}+2 F_{2}+3 F_{3}+\ldots+n F_{n}\right) \bmod m$ 表示 Fibonacci 数列前 $n$ 项变形后的和 $\bmod m$ 的值。现在佳佳告诉你了一个 $n$ 和 $m$, 请求出 $T(n)$ 的值。

思路

A矩阵中不能有变量，所以不能直接做

曲线救国的方法

代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 4;

int n, m;

void mul(int c[][N], int a[][N], int b[][N])  // c = a * b
{
    static int t[N][N];
    memset(t, 0, sizeof t);

    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] + (LL)a[i][k] * b[k][j]) % m;

    memcpy(c, t, sizeof t);
}

int main()
{
    cin >> n >> m;

    // {fn, fn+1, sn, pn}
    // pn = n * sn - tn
    int f1[N][N] = {1, 1, 1, 0};
    int a[N][N] = {
        {0, 1, 0, 0},
        {1, 1, 1, 0},
        {0, 0, 1, 1},
        {0, 0, 0, 1},
    };

    int k = n - 1;

    // 快速幂
    while (k)
    {
        if (k & 1) mul(f1, f1, a);  // f1 = f1 * a
        mul(a, a, a);  // a = a * a
        k >>= 1;
    }

    cout << (((LL)n * f1[0][2] - f1[0][3]) % m + m) % m << endl;

    return 0;
}