矩阵乘法

定义
其实就是两个矩阵第i行乘以第j列
推导是这样的，斐波那契数为例
https://blog.csdn.net/ganjingxian/article/details/77160271?tdsourcetag=s_pcqq_aiomsg
矩阵快速幂求Febo

 1 #include<iostream>
 2 #include<cstring> 
 3 #define MOD 10000
 4 using namespace std;
 5 struct sb
 6 {
 7     int a[2][2];
 8 };
 9 sb mul(sb x,sb y)
10 {
11     sb res;
12     memset(res.a,0,sizeof(res.a));
13     for (int i=0;i<2;i++)
14       for (int j=0;j<2;j++)
15         for (int k=0;k<2;k++)
16           res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[j][k])%MOD;
17     return res;
18 }
19 void mat_pow(int n)
20 {
21     sb res,c;
22     c.a[0][0]=c.a[0][1]=c.a[1][0]=1;
23     c.a[1][1]=0;
24     memset(res.a,0,sizeof(res.a));
25     for (int i=0;i<2;i++) res.a[i][i]=1;
26     while (n)
27     {
28         if (n&1!=0) res=mul(res,c);
29         c=mul(c,c);
30         n>>=1;
31     } 
32     cout<<res.a[0][1]<<endl;
33 }
34 int main ()
35 {
36     int n;
37     while(cin>>n&&n!=-1)
38         mat_pow(n);
39 }

为何要逼自己长大，去闯不该闯的荒唐

矩阵乘法

定义

矩阵快速幂求Febo