矩阵乘法相关

矩阵乘法

乘 A, B 得 C

C 中的 $[i][j]$ = A 中的第 $i$ 行和 B 中的第 $j$ 列相乘 YYH

例题

AcWing 1303. 斐波那契前 n 项和
设

$S_n = \sum_{i = 1}^{n} f_i \\ F_n = \begin{bmatrix}f_n & f_{n + 1} &S_n\end{bmatrix} \\ F_{n + 1} = \begin{bmatrix}f_{n + 1} & f_{n + 2} &S_{n + 1}\end{bmatrix}$

然后设

$F_i \times A = F_{i + 1}$

于是我们有

$F_n = F_1 \times A^{n - 1}$

问题迎刃而解
但是, 怎么求A?

根据定义， 我们需要 $A$ 中的每一列乘以对应的 $F$ 为下一个 $F$

于是

$A = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}$

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

using namespace std;

typedef long long LL;

const int N = 3;

int n, m;

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

    memcpy(c, temp, sizeof temp);
}

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

    memcpy(c, temp, sizeof temp);
}

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

    int f1[N] = {1, 1, 1};
    int a[N][N] = {
        {0, 1, 0},
        {1, 1, 1},
        {0, 0, 1}
    };

    n -- ;
    while (n)
    {
        if (n & 1) mul(f1, f1, a);  // res = res * a
        mul(a, a, a);  // a = a * a
        n >>= 1;
    }

    cout << f1[2] << endl;

    return 0;
}

Congratulations!

再看

AcWing 1304. 佳佳的斐波那契

矩阵也很好求

设

$T_n = \sum_{i = 1}^{n} i f_i \\ F_n = \begin{bmatrix}f_n & f_{n + 1} &n f_n & (n+1) f_{n + 1} & T_n\end{bmatrix} \\ F_{n + 1} = \begin{bmatrix}f_{n + 1} & f_{n + 2} & (n + 1) f_{n + 1} & (n + 2) f_{n + 2} & T_{n + 1}\end{bmatrix}$

然后设

$F_i \times A = F_{i + 1}$

于是我们有

$F_n = F_1 \times A^{n - 1}$

A 怎么求？

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

using namespace std;

typedef long long LL;

const int N = 5;

int n, m;

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

    memcpy(c, temp, sizeof temp);
}

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

    memcpy(c, temp, sizeof temp);
}

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

    int f1[N] = {1, 1, 1, 2, 1};
    int a[N][N] = {
		{0, 1, 0, 2, 0}, 
		{1, 1, 0, 1, 0},
		{0, 0, 0, 1, 0},
		{0, 0, 1, 1, 1},
		{0, 0, 0, 0, 1}
    };

    n -- ;
    while (n)
    {
        if (n & 1) mul(f1, f1, a);  // res = res * a
        mul(a, a, a);  // a = a * a
        n >>= 1;
    }

    cout << f1[4] << endl;

    return 0;
}