题意:
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循环节呢)!
法二:
队友说他是用矩阵快速幂写的,着实钦佩,因为已经是第二次写这道题了,看过寻找循环节的想法,思维受到了一定的局限。其实,坦白说,看数据量和时限,出题者的意图应该是想考察矩阵快速幂,虽然,找规律比较简单。但,不得不说,这样的想法,在现场是很难想出来的,较为直接的想法还是矩阵快速幂。所以说,学好基本功是最重要的。
一开始看到f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7这条式子,想着是这样构造。
想法很直接,但却犯了两个很严重的错误。1.1*2的矩阵与2*2的矩阵相乘仍是1*2的矩阵,而等式左边却是1*1的矩阵。2.虽然看上去符合递推关系,但是,一旦递推一项,就会发现不符合。
正确解法:
其实和上面也比较接近了,既然,要利用f(n-1)和f(n-2)递推得到f(n),那么出于矩阵规格考虑,f(n)势必还需要一项f(n-1),故可以推出矩阵构造如下:
第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; }