hdu4291 暴力循环节+矩阵快速幂

题意：
      给你一个关系式，x[n] = 3*x[n-1] + x[n-2],求x(x(x[n]))%1000000007.


思路：

      做这个题目要明确一点，就是对于取余操作大多数时候都会出现循环节的情况，尤其是对于像这个题目的转换公式，数据有规律递增，那么也就是说0 1 1 ....等再次出现0 1的时候也就是一定找了循环节，对于这个题目我们找循环节主要不是为了防止超时，而是为了得到正确的答案，因为x[n]很大的时候就的模拟大数，就麻烦了，我们只要找到每一层的循环节，就能把数据弄小，就可以跑三次矩阵快速A掉这个题目了。

下面给出暴力循环节代码（暴力第二层的，最内层把10..7改成第二层的MOD就行了）

#include<stdio.h>


int main ()
{
   __int64 a = 0 ,b = 1 ,c;
   for(__int64 i = 3 ; ;i ++)
   {
      c = (b * 3 + a)%1000000007;
      a = b ,b = c;
      if(a == 0 && b == 1)
      {
          printf("%I64d\n" ,i - 2);
          break;
      }
   }
   getchar();
   return 0;
}
      
暴力后得到最内侧的MOD = 183120
第二层 MOD = 222222224
最外层给了 MOD = 1000000007

AC代码

#include<stdio.h> #include<string.h> __int64 MOD1 = 183120; __int64 MOD2 = 222222224; __int64 MOD3 = 1000000007;__int64 MOD; typedef struct {__int64 mat[5][5]; }A;A mat_mat(A a ,A b) {A c;memset(c.mat ,0 ,sizeof(c.mat));for(int k = 1 ;k <= 2 ;k ++)for(int i = 1 ;i <= 2 ;i ++)if(a.mat[i][k])for(int j = 1 ;j <= 2 ;j ++)c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;return c; } A quick_mat(A a ,__int64 b) {A c;memset(c.mat ,0 ,sizeof(c.mat));c.mat[1][1] = c.mat[2][2] = 1;while(b){if(b & 1) c = mat_mat(c ,a);a = mat_mat(a ,a);b >>= 1;}return c; }int main () {__int64 n ,i;A aa ,bb;aa.mat[1][1] = 0 ,aa.mat[1][2] = 1;aa.mat[2][1] = 1 ,aa.mat[2][2] = 3;while(~scanf("%I64d" ,&n)){if(n == 0){printf("0\n");continue;}if(n == 1){printf("1\n");continue;}MOD = MOD1;bb = quick_mat(aa ,n - 1);n = (0 * bb.mat[1][2] + 1 * bb.mat[2][2])% MOD;if(n == 0){printf("0\n");continue;}if(n == 1){printf("1\n");continue;}MOD = MOD2;bb = quick_mat(aa ,n - 1);n = (0 * bb.mat[1][2] + 1 * bb.mat[2][2])% MOD;if(n == 0){printf("0\n");continue;}if(n == 1){printf("1\n");continue;}MOD = MOD3;bb = quick_mat(aa ,n - 1);n = (0 * bb.mat[1][2] + 1 * bb.mat[2][2])% MOD;printf("%I64d\n" ,n);}return 0; }

总结

以上是生活随笔为你收集整理的hdu4291 暴力循环节+矩阵快速幂的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。