【算法与数据结构】——矩阵快速幂

导引问题:
一个由0和1组成的字符串,任何字串都不能包含101和111,求满足要求的长度为L(1<=L<= $10^8$)的字符串有多少个?结果对$10^8$求模。
递推公式:f(n)=f(n-1)+f(n-3)+f(n-4)
n是字符串长度
字符串长度为1时,只有两个字符串且都满足要求:f(1)=2
字符串长度为2时,只有四个字符串且都满足要求:f(2)=4
字符串长度为3时,有8个字符串其中有两个不符合要求:f(3)=6
字符串长度大于三时,需要分类

• 结尾为0的字符串,前面所有满足要求的字符串此时也都满足要求f(n)=f(n-1)
• 结尾为1的字符串,前面两位只能是00或01
• 对于前两位是00的也就是字符串末尾3位是001的,前面的字符串可以是任意的合法字符串即f(n-3);
• 对于前两位是01的,也就是字符串后3位是011,倒数第四位只能是0,而不能是1,倒数第四位为0时,前面的字符串可以是任意的合法字符串,即f(n-4)
• 由此得到了最终的递推公式f(n)=f(n-1)+f(n-3)+f(n-4)

此时由于L的范围达到了亿级,计算量比较大,由此我们利用矩阵快速幂解决

快速幂运算

递归实现

int power(int a,int n)
{
	int ans;
	if(n==0) ans=1;
	else
	{
		ans=power(a*a,n/2);
		if(n%2==1) ans*=a;
	}
	return ans;
}

循环实现

int power(int a,int n)
{	int ans=1;
	while(n)
	{	if(n%2) ans=ans*a;
	a=a*a;
	n=n/2;
	}
	return ans;
}

矩阵快速幂

矩阵快速幂的构造

原始公式$f[n]=f[n-1]+f[n-2]$
对应的矩阵乘法公式
$$\left[\begin{array}{c}f[n]\\ f[n-1]\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\ast \left[\begin{array}{c}f[n-1]\\ f[n-2]\end{array}\right]$$
假设
$$C(n)=\left[\begin{array}{c}f[n]\\ f[n-1]\end{array}\right]B=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$$
则易得:$C(n)=B\ast C(n-1)$
$C(n)=B^{n-1}\ast C(1)$
最终只需要利用快速幂计算出$B^{n-1}$再做一次矩阵乘法即可;

矩阵乘法的通用构造方法

**关键:**构造出K*K的B矩阵,K是f[n]的递归深度
一、$C_n$第1行的f[n]与前面的项有什么关系，就在B矩阵的第1行填写对应的系数。
二、$C_n$第2行的f[n-1]通常在B矩阵中的对应项系数为1,其余为0;其它列类似处理即可。

例如：

对应的矩阵B是$\left[\begin{array}{cccc}3& 0& 5& 9\\ 1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\end{array}\right]$

2. $f(n)=a\ast f(n-1)+b\ast f(n-3)+c$
   对应的递推公式
   $$\left[\begin{array}{c}f[n]\\ f[n-1]\\ f[n-2]\\ c\end{array}\right]=\left[\begin{array}{cccc}a& 0& b& 1\\ 1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right]\ast \left[\begin{array}{c}f[n-1]\\ f[n-2]\\ f[n-3]\\ c\end{array}\right]={\left[\begin{array}{cccc}a& 0& b& 1\\ 1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right]}^{n-2}\ast \left[\begin{array}{c}f[2]\\ f[1]\\ f[0]\\ c\end{array}\right]$$