『算法-ACM 竞赛-数学』矩阵快速幂详解

引导：
我们之前都学快速幂：
矩阵也是可以相乘，方阵可以自乘，即乘幂运算。
作用：
将线性递推，优化$log_{2}n$
模板：

定义矩阵的阶

const int len = 15;

定义转移矩阵

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

矩阵乘法

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;
}

矩阵快速幂

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;
}

算法的难点是怎样写出转移矩阵：
一般的递推式

关于其他矩阵构造：