这里有个链接大家可以学习一下，个人水平有限，很菜，怕说的不好误导大家

https://www.cnblogs.com/Konjakmoyu/p/4821044.html

 

#include
     
      #include
      
       using namespace std;struct matrix{    int ss[2][2];}a,b;int mod = 10000; //矩阵乘法matrix multi(matrix a,matrix b){    matrix temp;    memset(temp.ss,0,sizeof(temp.ss));    for(int i = 0;i<2;i++)        for(int j = 0;j<2;j++)            for(int k = 0;k<2;k++)                temp.ss[i][j] = (temp.ss[i][j] + a.ss[i][k]*b.ss[k][j])%mod;    return temp;} //矩阵快速幂int fast_mod(int n){    b.ss[0][0] = b.ss[0][1] = b.ss[1][0] = 1;    b.ss[1][1] = 0;    a.ss[0][0] = a.ss[1][1] = 1;    a.ss[0][1] = a.ss[1][0] = 0;    while(n)    {        if(n&1)            a = multi(a,b);        b = multi(b,b);        n >>= 1;    }    return a.ss[0][0];}int main(){    int n;    while(cin>>n&&n!=-1)    {        if(n == 0)    cout<<0<