【HDU4291】矩阵快速幂（寻找循环节）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4291

题目大意：g(0) = 0，g(1) = 1， g(n) = 3g(n - 1) + g(n - 2)，给你一个n（0<=n<=10^18），求g(g(g(n))) mod （10⁹ + 7）。

解题思路：如果直接利用n做三次矩阵快速幂求解的话，无奈的WA了。因为三次快速幂对1000000007取模的话，超精度了。所以必须本地处理寻找每层的循环节，最外层最1000000007取模，则找到最外层的循环节是222222224，次外层对222222224取模，找到次外层循环节是183120。接下来利用这三个不同的mod进行三层快速幂。

PS：取模函数一定会出现会出现循环节，至于为什么内层可以利用外层的循环节，我也不知道，但是据说可以证明。

循环节，改mod就好了

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const long long mod=1000000007;
 8 
 9 int main()
10 {
11     long long t0=0, t1=1;
12     for(long long  i=1; ; i++)
13     {
14         t0=(3*t1+t0)%mod;
15         swap(t0,t1);
16         if(t0==0&&t1==1)
17         {
18             cout << i <<endl;
19             break;
20         }
21     }
22 }

AC代码

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 typedef long long lld;
 9 
10 struct Maxtri
11 {
12     lld mat[2][2];
13 } A, B;
14 
15 void init()
16 {
17     A.mat[0][0]=1, A.mat[0][1]=0;
18     A.mat[1][0]=0, A.mat[1][1]=0;
19     B.mat[0][0]=3, B.mat[0][1]=1;
20     B.mat[1][0]=1, B.mat[1][1]=0;
21 }
22 
23 Maxtri Maxtri_mul(Maxtri a, Maxtri b, lld mod)
24 {
25     Maxtri c;
26     for(int i=0; i<2; i++)
27         for(int j=0; j<2; j++)
28         {
29             c.mat[i][j]=0;
30             for(int k=0; k<2; k++)
31                 c.mat[i][j]+=(a.mat[i][k]*b.mat[k][j])%mod;
32             c.mat[i][j]%=mod;
33 
34         }
35     return c;
36 }
37 
38 lld Maxtri_mi(lld b, lld mod)
39 {
40     if(b==0) return 0;
41     Maxtri ans=A, a=B;
42     b--;
43     while(b)
44     {
45         if(b&1) ans=Maxtri_mul(ans,a,mod);
46         b>>=1;
47         a=Maxtri_mul(a,a,mod);
48     }
49     return ans.mat[0][0];
50 }
51 
52 int main()
53 {
54     lld n, ans;
55     init();
56     while(~scanf("%I64d",&n))
57     {
58         ans=Maxtri_mi(n,183120);
59         ans=Maxtri_mi(ans,222222224);
60         ans=Maxtri_mi(ans,1000000007);
61         printf("%I64d\n",ans);
62     }
63 }

【HDU4291】 矩阵快速幂（寻找循环节）

【HDU4291】矩阵快速幂（寻找循环节）