hdu 4291(矩阵+暴力求循环节)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4291
思路：首先保留求出循环节，然后就是矩阵求幂了。
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef __int64 ll;
 7 #define MOD2 1000000007
 8 #define MOD1 222222224
 9 #define MOD0 183120
10 
11 /*
12 暴力求循环节
13 int main()
14 {
15     ll f0=0,f1=1;
16     for(ll i=1; ;i++){
17         ll tmp=(3*f1+f0)%MOD1;
18         f0=f1;
19         f1=tmp;
20         if(f0==0&&f1==1){
21             printf("%I64d
",i);
22             break;
23         }
24     }
25     return 0;
26 }*/
27 
28 ll n;
29 
30 struct Matrix{
31     ll map[2][2];
32 }Mata,Matb;
33 
34 Matrix Mul(const Matrix &a,const Matrix &b,ll MOD)
35 {
36     Matrix c;
37     for(int i=0;i<2;i++){
38         for(int j=0;j<2;j++){
39             c.map[i][j]=0;
40             for(int k=0;k<2;k++){
41                 c.map[i][j]+=a.map[i][k]*b.map[k][j];
42                 if(c.map[i][j]>=MOD)c.map[i][j]%=MOD;
43             }
44         }
45     }
46     return c;
47 }
48 
49 ll Pow(Matrix p,ll n,ll MOD)
50 {
51     Matrix q;
52     for(int i=0;i<2;i++)
53         for(int j=0;j<2;j++)
54             q.map[i][j]=(i==j?1:0);
55     while(n){
56         if(n&1){
57             q=Mul(p,q,MOD);
58         }
59         n>>=1;
60         p=Mul(p,p,MOD);
61     }
62     return q.map[0][1];
63 }
64 
65 int main()
66 {
67     while(~scanf("%I64d",&n)){
68         if(n==0){
69             puts("0");
70         }else if(n==1){
71             puts("1");
72         }else {
73             Mata.map[0][0]=3;
74             Mata.map[0][1]=1;
75             Mata.map[1][0]=1;
76             Mata.map[1][1]=0;
77             ll tmp1=Pow(Mata,n,MOD0);
78             ll tmp2=Pow(Mata,tmp1,MOD1);
79             ll tmp3=Pow(Mata,tmp2,MOD2);
80             printf("%I64d
",tmp3);
81         }
82     }
83     return 0;
84 }
View Code