HDU 4291 A Short problem(循環節を探す+高速べき乗行列)
13146 ワード
タイトルリンク
アルゴリズムを知っている場合、行列を書いたアルゴリズムはループ節を探しに行き、10分ほど走っても結果が出ませんでした...真心2 Bですね...このような利用サイクルの最適化をよく理解する.
アルゴリズムを知っている場合、行列を書いたアルゴリズムはループ節を探しに行き、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 */