矩阵快速幂

0.矩阵的代码表示

struct node {
	int mat[15][15];
}x,y; 

1.矩阵乘法

矩阵乘法（就是线性代数里学过那个）是对矩阵的一种基本运算，仅当矩阵A列数与矩阵B行数相等时A*B才有意义。由A(m,n)*B(n,p)可得到C(m,p)；矩阵乘法满足结合律与分配律，但不满足交换律，因为比较简单所以这里就不详细讲了。
例题：

   node mul(node x,node y){
	node tmp;
	for(int i=0;i<len;i++){
		for(int j=0;j<len;j++){
			tmp.mat [i][j]=0;
			for(int k=0;k<len;k++){
				tmp.mat [i][j]+=(x.mat [i][k]*y.mat [k][j])%mod;
			}
			tmp.mat [i][j]=tmp.mat[i][j]%mod;
		}
	}
	return tmp;
} 

注意：方阵也不满足交换律

2.快速幂

比较简单，话不多说直接上代码

int Pow(int a,int b){
    int ans = 1;
    int base = a;
    while(b){
        if(b & 1) ans *= base;
        base *= base;
        b >>= 1;
    }
    return ans;
}

需要取模：

#define mod 1000000007
int pow_mod(int a,int b){
    int ans = 1;
    int base = a%mod;
    while(b){
        if(b & 1) ans = (ans*base)%mod;
        base = (base*base)%mod;
        b >>= 1;
    }
    return ans;
}

3.矩阵快速幂

矩阵快速幂就是用矩阵乘法来加速快速幂啦。实际上用方阵就好了。

    node matpow(node x,node y,int num){
    	while(num){
    		if(num&1){
    			y=mul(y,x);
    		}
    		x=mul(x,x);
    		num=num>>1;
    	}
    	return y;
    } 

学废完了之后可以试着用这种方法去解决一下斐波那契数列超时问题