首页 > 代码库 > HDU 1005矩阵快速幂解法 循环节解法
HDU 1005矩阵快速幂解法 循环节解法
循环节解法：
对于公式 f[n] = A * f[n-1] + B * f[n-2]; 后者只有7 * 7 = 49 种可能，为什么这么说，因为对于f[n-1] 或者 f[n-2] 的取值只有 0,1,2,3,4,5,6 这7个数，A，B又是固定的，所以就只有49种可能值了。由该关系式得知每一项只与前两项发生关系，所以当连续的两项在前面出现过，由于公式不变，那么后面得到的一定是跟前面相重复的。所以这个时候循环节就出现了，注意循环节并不一定会是开始的 1，1；但1，1一定可以作为一个循环节，只不过可能不是最高出现的循环节。又因为一组测试数据中f[n]只有49中可能的答案，最坏的情况是所有的情况都遇到了，那么那也会在50次运算中产生循环节。找到循环节后，就可以轻松解决了。这里，直接采用1，1作为循环节来判断，代码：
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 int main() 5 { 6 int a,b,n,i; 7 int m[1000]; 8 while(scanf("%d%d%d",&a,&b,&n),(a||b||n)) 9 {10 m[1] = 1;11 m[2] = 1;12 for(i = 3;i < 1000;i++)13 {14 m[i] = (a*m[i-1]+b*m[i-2])%7;15 if(m[i]==1 && m[i-1]==1)16 break;17 }18 m[0] = m[i-2];19 /*printf("%d\n",(i-2));*/20 n = n%(i-2);21 printf("%d\n",m[n]);22 }23 return 0;24 }
矩阵快速幂解法：
根据递推公式f(n) = A*f(n-1)+Bf(n-2)来构造矩阵。同普通数字的快速幂一样，矩阵的幂也可以用类似的方法来计算，只不过此时相乘的是矩阵了。代码：
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 typedef struct Mat{ 5 int num[3][3]; 6 }Mat; 7 8 Mat Mult(Mat a,Mat b) /*Matrix a multi Matrix b*/ 9 {10 int i,j,k;11 Mat c;12 for(i=0 ;i<2 ;i++)13 for(j=0 ;j<2 ;j++)14 {15 c.num[i][j] = 0;16 for(k=0 ;k<2 ;k++)17 c.num[i][j] = (c.num[i][j] + a.num[i][k]*b.num[k][j])%7; /*mod 7*/18 }19 return c;20 }21 22 Mat Mat_pow(Mat a,int n) /*Matrix Quick power n*/23 {24 Mat Result;25 Result.num[0][0] = 1;26 Result.num[0][1] = 0;27 Result.num[1][0] = 0;28 Result.num[1][1] = 1;29 while(n != 0){30 if(n & 1)31 Result = Mult(Result,a);32 a = Mult(a,a);33 n >>= 1;34 }35 return Result;36 }37 38 int main()39 {40 int a,b;41 int n;42 Mat A;43 while(scanf("%d%d%d",&a,&b,&n),(a||b||n))44 {45 A.num[0][0] = a;46 A.num[0][1] = b;47 A.num[1][0] = 1;48 A.num[1][1] = 0;49 if(n==1 || n==2)50 {51 printf("1\n");52 continue; /*can not be break*/53 }54 A = Mat_pow(A,n-2);55 printf("%d\n",(A.num[0][0]+A.num[0][1])%7);56 }57 return 0;58 }
HDU 1005矩阵快速幂解法 循环节解法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。