题意：
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，则不乘，次方矩阵（姑且容我这么叫吧）则需不断自乘，以配合二进制挪位。
总结：
代码：
#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;elseans.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;}
只有经历过地狱般的折磨，才有征服天堂的力量。
