# 矩阵乘法与矩阵快速幂 求斐波那契数列第 n 项

2018 年 7 月 16 日 09:52

## 矩阵

### 定义

$\begin{bmatrix} 1 & 2 & 3 \\\\ 4 & 6 &5 \end{bmatrix}$

### 矩阵的加减法

$\begin{bmatrix} 1 & 2 & 3 \\\\ 4 & 6 & 5 \end{bmatrix} + \begin{bmatrix} 2 & 1 & 0 \\\\ 2 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 3 & 3 & 3 \\\\ 6 & 6 & 6 \end{bmatrix}$

### 矩阵乘以矩阵

$AB_{ij} = \sum_{r=1}^{n}a_{ir}b_{rj}= a_{i1}b_{1j}+a_{i2}b_{2j}+\dots+a_{in}b_{nj}$

$\begin{bmatrix} 1 & 2 \\\\ 4 & 3 \end{bmatrix} + \begin{bmatrix} 2 & 1 \\\\ 2 & 0 \end{bmatrix} = \begin{bmatrix} 3 & 3 \\\\ 6 & 6 \end{bmatrix}$

## 矩阵快速幂求斐波那契数列

$\begin{bmatrix} F_{n+1} & F_n \\\\ F_n & F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\\\ 1 & 0 \end{bmatrix}^n = \underbrace{ \begin{bmatrix} 1 & 1 \\\\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & 1 \\\\ 1 & 0 \end{bmatrix}\cdots \begin{bmatrix} 1 & 1 \\\\ 1 & 0 \end{bmatrix} }_ {\text{n times}}$

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

## 例题

### 综合

CodeForces 551D. GukiZ and Binary Operations

## 代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=105,tt=1000000007;;
int n;
long long m;
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
struct Matrix{
int a[maxn][maxn];
memset(a,0,sizeof(a));
for (int i=0;i<n;i++)
for (int j=0;j<n;j++) a[i][j]=read();
}
void Init(){
memset(a,0,sizeof(a));
for (int i=0;i<n;i++) a[i][i]=1;
}
void Clear(){
memset(a,0,sizeof(a));
}
Matrix operator *(Matrix b){
Matrix c; c.Clear();
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
for (int k=0;k<n;k++)
c.a[i][j]=((long long)c.a[i][j]+(long long)a[i][k]*b.a[k][j])%tt;
return c;
}
Matrix operator ^(long long b){
Matrix ret; ret.Init();
Matrix w;   w.Clear();
for (int i=0;i<n;i++)
for (int j=0;j<n;j++) w.a[i][j]=a[i][j];
while (b){
if (b%2) ret=ret*w;
b=b/2;w=w*w;
}
return ret;
}
void Write(){
for (int i=0;i<n;i++){
for (int j=0;j<n;j++) printf("%d ",a[i][j]);
printf("\n");
}
}
};
int main(){
// printf("Read part finished.\n");
a=a^m;
a.Write();
return 0;
}


#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int tt=10000;
int n;
struct Matrix{
int a[3][3];
void Init(){
memset(a,0,sizeof(a));
a[0][0]=a[1][0]=a[0][1]=1;
a[1][1]=0;
}
void Clear(){
memset(a,0,sizeof(a));
}
Matrix operator *(Matrix b){
Matrix c; c.Clear();
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
for (int k=0;k<2;k++)
c.a[i][j]=((long long)c.a[i][j]+(long long)a[i][k]*b.a[k][j])%tt;
return c;
}
Matrix operator ^(long long b){
Matrix ret; ret.Init();
Matrix w;   w.Clear();
for (int i=0;i<2;i++)
for (int j=0;j<2;j++) w.a[i][j]=a[i][j];
while (b){
if (b%2) ret=ret*w;
b=b/2;w=w*w;
}
return ret;
}
void Write(){
for (int i=0;i<2;i++){
for (int j=0;j<2;j++) printf("%d ",a[i][j]);
printf("\n");
}
}
};
int main(){
scanf("%d",&n);n--;
while (n!=-2){
if (n==-1) printf("0\n"); else{
Matrix a; a.Init();
a=a^n;
printf("%d\n",a.a[1][0]);
}
scanf("%d",&n);n--;
}
return 0;
}