HDU 4291 A Short problem(循環節を探す+高速べき乗行列)

13146 ワード

タイトルリンク
アルゴリズムを知っている場合、行列を書いたアルゴリズムはループ節を探しに行き、10分ほど走っても結果が出ませんでした...真心2 Bですね...このような利用サイクルの最適化をよく理解する.
 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstring>

 4 #include <cmath>

 5 #include <cstdlib>

 6 using namespace std;

 7 #define LL __int64

 8 int len1 = 222222224,len2 = 183120;

 9 LL p[3][3],mat[3][3];

10 LL qmod(LL n,LL MOD)

11 {

12     int i,j,k;

13     LL c[3][3];

14     while(n)

15     {

16         if(n&1)

17         {

18             memset(c,0,sizeof(c));

19             for(i = 1; i <= 2; i ++)

20                 for(j = 1; j <= 2; j ++)

21                     for(k = 1; k <= 2; k ++)

22                     {

23                         c[i][j] = (c[i][j]+(mat[i][k]*p[k][j])%MOD)%MOD;

24                     }

25             memcpy(mat,c,sizeof(mat));

26         }

27         memset(c,0,sizeof(c));

28         for(i = 1; i <= 2; i ++)

29             for(j = 1; j <= 2; j ++)

30                 for(k = 1; k <= 2; k ++)

31                 {

32                     c[i][j] = (c[i][j]+(p[i][k]*p[k][j])%MOD)%MOD;

33                 }

34         memcpy(p,c,sizeof(p));

35         n >>= 1;

36     }

37     return mat[1][1]%MOD;

38 }

39 int main()

40 {

41     int i,j,k;

42     LL n;

43 

44     while(scanf("%I64d",&n)!=EOF)

45     {

46         for(k = 1; k <= 3; k ++)

47         {

48             memset(p,0,sizeof(p));

49             memset(mat,0,sizeof(mat));

50             p[1][1] = 3;

51             p[1][2] = p[2][1] = 1;

52             p[2][2] = 0;

53             for(i = 1; i <= 2; i ++)

54                 for(j = 1; j <= 2; j ++)

55                     if(i == j)

56                         mat[i][j] = 1;

57                     else

58                         mat[i][j] = 0;

59             if(n == 0||n == 1)

60             {

61                 continue;

62             }

63             if(k == 1)

64             n = qmod(n-1,len2);

65             else if(k == 2)

66             n = qmod(n-1,len1);

67             else if(k == 3)

68             n = qmod(n-1,1000000007);

69         }

70         printf("%I64d
",n); 71 } 72 return 0; 73 } 74 // 75 /* 76 #include <stdio.h> 77 int main() 78 { 79 LL i,j,k,t; 80 j = 1;k = 0; 81 for(i = 2;i <= 1000000000;i ++) 82 { 83 t = j; 84 j = (3*j + k)%222222224; 85 k = t; 86 if(j == 1&&k == 0) 87 { 88 printf("%d
",i);
89 break; 90 } 91 } 92 return 0; 93 } 94 */