题目大意

输出$Fibonacci$数列第$k$项除以$10000$的余数

数据范围

$1\leqslant k\leqslant 10^9$

题解

第一道矩阵乘法，模板题感觉还好

直接用矩阵乘法即可，最后输出最终矩阵的左下角或者右上角

矩阵乘法一些定义与性质

设$A=(a_{ij})$为$m\times p$的矩阵，$B=(b_{ij})$为$p\times n$的矩阵，那么称$m\times n$的矩阵$C=(c_{ij})$为矩阵$A$与$B$的乘积，记作$C=AB$

有这样三个定义

1. 当$A$的列数等于$B$的行数时，$A$与$B$可以相乘

2. $C$的行数等于$A$的行数，$C$的列数等于$B$的列数

3. $C$的第$i$行第$j$列的元素等于$A$的第$i$行的元素与$B$的第$j$列对应元素乘积之和

由定义可以得到矩阵乘法的一些性质

1. $AB\neq BA$，即矩阵乘法不符合交换律

2. $(AB)C=A(BC)$，即矩阵乘法符合结合律

因为矩阵乘法符合结合律，所以我们可以改变乘法的顺序，也就可以用快速幂迅速求出矩阵乘法的结果

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int k,a[3][3],ans[3][3];
inline void mul(int a[3][3],int b[3][3],int result[3][3]){
    int c[3][3];memset(c,0,sizeof(c));
    For(i,1,2) For(j,1,2)
        For(p,1,2) c[i][j]=(c[i][j]+a[i][p]*b[p][j])%10000;
    For(i,1,2) For(j,1,2) result[i][j]=c[i][j];
}

int main(){
    while (1){
        k=read();
        if (k==-1) break;
        if (k==0) {puts("0");continue;}
        a[1][1]=a[1][2]=a[2][1]=1,a[2][2]=0;
        ans[1][1]=ans[2][2]=1,ans[1][2]=ans[2][1]=0;
        while (k){
            if (k&1) mul(a,ans,ans);
            k>>=1;mul(a,a,a);
        }
        printf("%d\n",ans[2][1]);
    }
    return 0;
}