ZOJ 2105 Number Sequence(矩阵快速幂)

时间:2022-06-14 22:19:02

题意:

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

给定A,B,求f(n)。

法一:

         网上较多的题解都提到了寻找1 1循环节的方法,的确非常巧妙,每位0~6,共7种可能,相邻两位共49种可能,因此循环周期至多为49,一旦出现相同数对,那么其后必相同。但是,该方法只是简单提及了49,却并没有证明1 1循环节一定存在,没有排除可能前面一段不循环,后面一段开始周期性循环的可能性。(是我悟性太差吗,为什么大多数题解都只谈及寻找1 1循环节呢ZOJ 2105 Number Sequence(矩阵快速幂))!


法二:

        队友说他是用矩阵快速幂写的,着实钦佩,因为已经是第二次写这道题了,看过寻找循环节的想法,思维受到了一定的局限。其实,坦白说,看数据量和时限,出题者的意图应该是想考察矩阵快速幂,虽然,找规律比较简单。但,不得不说,这样的想法,在现场是很难想出来的,较为直接的想法还是矩阵快速幂。所以说,学好基本功是最重要的。

        一开始看到f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7这条式子,想着是这样构造。

ZOJ 2105 Number Sequence(矩阵快速幂)

        想法很直接,但却犯了两个很严重的错误。1.1*2的矩阵与2*2的矩阵相乘仍是1*2的矩阵,而等式左边却是1*1的矩阵。2.虽然看上去符合递推关系,但是,一旦递推一项,就会发现不符合。

        正确解法:

        其实和上面也比较接近了,既然,要利用f(n-1)和f(n-2)递推得到f(n),那么出于矩阵规格考虑,f(n)势必还需要一项f(n-1),故可以推出矩阵构造如下:

ZOJ 2105 Number Sequence(矩阵快速幂)

        第3个矩阵左半部分很好想,右半部分根据等式左边的形式可以推出1 0。矩阵构造好之后,就是直接利用矩阵快速幂求解了。矩阵快速幂的思想很简单,就是将指数分解成2进制,当那一位2进制为1时,就将矩阵乘以当前的次方矩阵,若为0,则不乘,次方矩阵(姑且容我这么叫吧)则需不断自乘,以配合二进制挪位。

总结:

         矩阵相乘满足结合律,不满足交换律。矩阵快速幂,涉及到一个矩阵的n次方,因此该矩阵要满足自乘的性质,故必为方阵。构造矩阵时,可以结合这一点构造。


代码:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct Matrix
{
   int num[2][2];	
};
//矩阵相乘 
Matrix mult(Matrix a,Matrix b)
{
	Matrix ans;
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
		{
			ans.num[i][j]=0;
			for(int k=0;k<2;k++)
			{
				ans.num[i][j]=(ans.num[i][j]+a.num[i][k]*b.num[k][j])%7;
			}
		}
	}
	return ans;
}
//矩阵幂 
Matrix Mat_pow(Matrix x,int y)
{
	Matrix ans;
    //初始化单位矩阵 
	for(int i=0;i<2;i++)
	{
        for(int j=0;j<2;j++)
	    {
            if(i==j)
                ans.num[i][j]=1;
            else
                ans.num[i][j]=0;
        }
	}
	//二进制求解过程 
	for(;y;y>>=1)
	{
      if(y&1)ans=mult(ans,x);
        x=mult(x,x);
    } 
	return ans;
}
int main()
{
	int a,b,y;
	while(scanf("%d%d%d",&a,&b,&y)&&(a||b||y))
	{
		if(y==1||y==2)
		{
			cout<<1<<endl;
			continue;
		} 
		//构造矩阵 
		else
		{
			Matrix x,ans;
			x.num[0][0]=a;
			x.num[0][1]=1;
			x.num[1][0]=b;
			x.num[1][1]=0;
			ans=Mat_pow(x,y-2);
			cout<<(ans.num[0][0]+ans.num[1][0])%7<<endl;
		}
	}
	return 0;
}