## 矩阵

### 定义

\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}

### 矩阵乘以矩阵

\displaystyle 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}

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

\displaystyle
\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}}

## 例题

### 综合

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;
}