先来看看矩阵乘法的定义：
设 $A$ 是 $n*m$ 矩阵，$B$ 是 $m*p$ 矩阵， 则 $C=A*B$ 是 $n*p$ 矩阵，并且 $C_{i,j}=\sum\limits_{i=1}^nA_{i,k}*B_{k,j}$。
已知矩阵乘法满足交换律，即有 $(A*B)*C=A*(B*C)$。
光看这些看不懂，讲些例题看看能不能看懂。
Fibonacci求和
大家知道Fibonacci数列吧, $f[1]=1, f[2]=1, f[3]=2, f[4]=3\ldots$, 也就是 $f[n]=f[n-1]+f[n-2]$， 现在问题很简单，输入 $n$ 和$m$，求前 $n$ 项和取模$m$。
solution
首先知道一个要点，$S_n=f_{n+2}-1$，现在可以将问题简化成“求第 $n+2$ 项减去一并取模$m$”。
我们构造一个矩阵，设 $F(n)$ 表示一个 $1*2$ 的矩阵，$F(n)=[Fib_n Fib_{n+1}]$。我们希望根据 $F(n-1)=[Fib_{n-1},Fib_n]$ 计算出 $F(n)$。
我们再构造一个 $A$。注意看，根据定义，$F(n)_0=A_{0,0}*F(n-1)_0+A_{1,0}*F(n-1)_1,F(n)_1=A_{0,1}*F(n-1)_1+A_{1,1}*F(n-1)_0$。那么我们推出 $A_{0,0}=0,A_{0,1}=1,A_{1,0}=1,A_{1,1}=1$。于是，初始化 $F(0)=[0,1]$，目标为 $F(n)=A^n*F(0)$，因为矩阵乘法满足结合律，所以我们可以用快速幂计算 $F(0)*A^n$。
那么话不多说，代码开冲。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
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] + (ll)f[k] * a[k][j]) % m;
memcpy(f, c, sizeof(c));
}
void mulself(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] + (ll)a[i][k] * a[k][j]) % m;
memcpy(a, c, sizeof(c));
}
int main() {
cin >> n >> m;
int f[2] = {0, 1};
int a[2][2] = {{0, 1}, {1, 1}};
n += 2;
while(n) {
if(n & 1)
mul(f, a);
mulself(a);
n >>= 1;
}
cout << f[0] - 1 << endl;
return 0;
}
佳佳的斐波那契
佳佳对数学，尤其数列十分感兴趣，在研究完 $Fibonacci$ 之后，他创造出许多稀奇古怪的数列。如求 $S(n)$ 表示 $Fibonacci$ 数列前 $n$ 项和对 $m$ 取模之后的值，即 $S(n)=(F1+F2+…+Fn) \bmod m$，$F1=F2=1$。可是这对佳佳来说还是小菜一碟。终于，他找到一个自己解决不了的数列。。。$T(n)$ 表示 $Fibonacci$ 数列前 $n$ 项变形后的和对 $m$ 取模之后的值，即 $T(n)=(F1+2*F2+3*F3+…+n*Fn) \bmod m，F1=F2=1$。
Solution
第一种是数学 $+$ 矩阵乘法，通过推算可以推出 $T_n=n*F(n+2)-F(n+3)+2$，有兴趣的同学可以尝试自己推算，这里不多赘述。
第二种是纯矩阵乘法，我们假设 $F(n)=[T_n,T_{n - 1},T_{n - 2},fib_{n + 1},fib_n]$，为什么这么假设呢？下面开始推导：
易知 $F(n)_1=T_n$，这是我们推导的基础，但 $T_n=\sum _ {i = 1} ^ n fib_i*i$ 并不是我们所要的常数项递推公式，下面给出推导过程：
预备公式：$fib_n*n=T_{n}-T_{n-1}$，推导过程包含在整个推导过程中。
$T_n=\sum _ {i = 1} ^ n fib_i*i$
$ =(\sum _ {i = 1} ^ {n-1} fib_i*i)+fib_n*n$
$ =T_{n-1}+fib_n*n$
$ =T_{n-1}+fib_n*(n-1)+fib_n$
$ =T_{n-1}+fib_{n-1}*(n-1)+fib_{n-2}*(n-2)+fib_{n-2}+fib_n$
$ =T_{n-1}+T_{n-1}-T_{n-2}+T_{n-2}-T_{n-3}+fib_n-fib_{n-1}+fib_n$
$ =2*T_{n-1}+0*T_{n-2}+(-1)*T_{n-3}+2*fib_n+(-1)*fib_{n-1}$
于是：
$T_n=2*T_{n-1}+0*T_{n-2}+(-1)*T_{n-3}+2*fib_n+(-1)*fib_{n-1}$，
$T_{n-1}=1*T_{n-1}+0*T_{n-2}+0*T_{n-3}+0*fib_n+0*fib_{n-1}$，
$T_{n-2}=0*T_{n-1}+1*T_{n-2}+0*T_{n-3}+0*fib_n+0*fib_{n-1}$，
$fib_{n+1}=0*T_{n-1}+0*T_{n-2}+0*T_{n-3}+1*fib_n+1*fib_{n-1}$，
$fib_n=0*T_{n-1}+0*T_{n-2}+0*T_{n-3}+1*fib_n+0*fib_{n-1}$。
因此构造系数矩阵：
$2,0,-1,2,-1$
$1,0,0,0,0$
$0,1,0,0,0$
$0,0,0,1,1$
$0,0,0,1,0$
然后将这个系数矩阵的第 $i$ 行作为 $a$ 的第 $i$ 列，便得到了我们的矩阵。
$2,1,0,0,0$
$0,0,1,0,0$
$-1,0,0,0,0$
$2,0,0,1,1$
$-1,0,0,1,0$
结合上一道题的代码，改写矩阵即可，注意当 $n = 1$ 时要特判。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
void mul(int f[5], int a[5][5]) {
int c[5];
memset(c, 0, sizeof(c));
for(int j = 0; j < 5; ++j)
for(int k = 0; k < 5; ++k)
c[j] = (c[j] + (ll)f[k] * a[k][j]) % m;
memcpy(f, c, sizeof(c));
}
void mulself(int a[5][5]) {
int c[5][5];
memset(c, 0, sizeof(c));
for(int i = 0; i < 5; ++i)
for(int j = 0; j < 5; ++j)
for(int k = 0; k < 5; ++k)
c[i][j] = (c[i][j] + (ll)a[i][k] * a[k][j]) % m;
memcpy(a, c, sizeof(c));
}
int main() {
scanf("%d%d", &n, &m);
if (n == 1) {
cout << 1 % m << endl;
return 0;
}
int f[5] = {3, 1, 0, 2, 1};
int a[5][5] = {{2, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {-1, 0, 0, 0, 0}, {2, 0, 0, 1, 1}, {-1, 0, 0, 1, 0}};
n -= 2;
while(n) {
if(n & 1)
mul(f, a);
mulself(a);
n >>= 1;
}
cout << (f[0] + m) % m << endl;
return 0;
}
序列递推
定义序列: $f[1]=f[2]=1, f[i]=f[i-1]+f[i-2]+i^3+1(i>2)$。 给定 $n$，请求 $f[n]$ 对 $10^9+7$ 取模的结果。
Solution
预备公式：$(a+b)^3=a^3+3a^2b+3ab^2+b^3$
还是一样，先推 $f_n$：
$f_n=f_{n-1}+f_{n-2}+i^3+1$
$=f_{n-1}+f_{n-2}+(i-1)^3+3(i-1)^2+3(i-1)+1+1$
$=1*f_{n-1}+1*f_{n-2}+1*(i-1)^3+3*(i-1)^2+3*(i-1)+2*(i-1)^0$
再写出所有项的公式：
$f_n=1*f_{n-1}+1*f_{n-2}+1*(i-1)^3+3*(i-1)^2+3*(i-1)+2*(i-1)^0$
$f_{n-1}=1*f_{n-1}+0*f_{n-2}+0*(i-1)^3+0*(i-1)^2+0*(i-1)+0*(i-1)^0$
$i^3=0*f_{n-1}+0*f_{n-2}+1*(i-1)^3+3*(i-1)^2+3*(i-1)+1*(i-1)^0$
$i^2=0*f_{n-1}+0*f_{n-2}+0*(i-1)^3+1*(i-1)^2+2*(i-1)+1*(i-1)^0$
$i=0*f_{n-1}+0*f_{n-2}+0*(i-1)^3+0*(i-1)^2+1*(i-1)+1*(i-1)^0$
$i^0=0*f_{n-1}+0*f_{n-2}+0*(i-1)^3+0*(i-1)^2+0*(i-1)+1*(i-1)^0$
写出系数矩阵：
$1,1,1,3,3,2$
$1,0,0,0,0,0$
$0,0,1,3,3,1$
$0,0,0,1,2,1$
$0,0,0,0,1,1$
$0,0,0,0,0,1$
写出矩阵 $a$：
$1,1,0,0,0,0$
$1,0,0,0,0,0$
$1,0,1,0,0,0$
$3,0,3,1,0,0$
$3,0,3,2,1,0$
$2,0,1,1,1,1$
套框架，写出代码：
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
ll n;
void mul(int f[6], int a[6][6]) {
int c[6];
memset(c, 0, sizeof(c));
for (int j = 0; j < 6; ++j)
for (int k = 0; k < 6; ++k) c[j] = (c[j] + (ll)f[k] * a[k][j] % mod) % mod;
memcpy(f, c, sizeof(c));
}
void mulself(int a[6][6]) {
int c[6][6];
memset(c, 0, sizeof(c));
for (int i = 0; i < 6; ++i)
for (int j = 0; j < 6; ++j)
for (int k = 0; k < 6; ++k) c[i][j] = (c[i][j] + (ll)a[i][k] * a[k][j] % mod) % mod;
memcpy(a, c, sizeof(c));
}
int main() {
scanf("%lld", &n);
/*令f[6] = {f[i], f[i - 1], i ^ 3, i ^2, i, 1}*/
int f[6] = { 1, 1, 8, 4, 2, 1 };
int a[6][6] = { { 1, 1, 0, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 }, { 1, 0, 1, 0, 0, 0 },
{ 3, 0, 3, 1, 0, 0 }, { 3, 0, 3, 2, 1, 0 }, { 2, 0, 1, 1, 1, 1 } };
n -= 2LL;
while (n) {
if (n & 1LL)
mul(f, a);
mulself(a);
n >>= 1LL;
}
printf("%d\n", f[0]);
return 0;
}
总结
以上只是矩阵乘法的简单问题，更多的难的题目后期会继续讲解，感谢大家的观看，希望能对大家产生帮助。
注：矩阵乘法模板会在后续给出。
