矩阵快速幂入门

首先理一理快速幂之前总结过但没记录下来

首先对于 $a^{n}$ 将n看成二进制的形式比如 $a^{010110111}$ 那么 $a^{1}$ $\times a^{1} \equiv a^{10}$ 以此类推每一位都会判断一遍是否是1 是就乘起来

现在在来讲矩阵快速幂：

首先现代知识矩阵乘法（直接上代码）：

void multi(int a[][MAX],int b[][MAX]){
    int temp[3][3];
    memset(temp,0,sizeof(temp));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                temp[i][j]=(temp[i][j]+(a[i][k]*b[k][j]))%mod;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            a[i][j]=temp[i][j];
}

显然矩阵快速幂就是求矩阵的幂代码：

void Pow(int a[][MAX],int n){
    memset(res,0,sizeof(res));
    for(int i=0;i<2;i++) res[i][i]=1;
    while(n){
        if(n&1){
            multi(res,a);
        }
        multi(a,a);
        n>>=1;
    }
}

那么我们再来讲应用：

斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

f(x)=f(x-1)+f(x-2);

用矩阵表示及：

(重点) 有点类似于转移方程；

那么前一个以此递推可以得到一个等比数列 $a_{n}=a_{1}\bullet T^{n-1}$

接下来就和快速幂一个道理了然后输出对应n位的值

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAX=3;
const int mod=1e4;
void multi(int a[][MAX],int b[][MAX]){
    int temp[3][3];
    memset(temp,0,sizeof(temp));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                temp[i][j]=(temp[i][j]+(a[i][k]*b[k][j]))%mod;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            a[i][j]=temp[i][j];
}
int res[MAX][MAX];
void Pow(int a[][MAX],int n){
    memset(res,0,sizeof(res));
    for(int i=0;i<2;i++) res[i][i]=1;
    while(n){
        if(n&1){
            multi(res,a);
        }
        multi(a,a);
        n>>=1;
    }
}
int main(){

    int n;
    while(scanf("%d",&n)!=EOF&&n!=-1){
        int T[MAX][MAX]={{1,1},{1,0}};
        Pow(T,n);
        printf("%d\n",res[0][1]);
    }
}