数学题，找循环节！！
首先g(g(g(n)))=g(x) mod 1e9+7 则可知x有循环节1e9+7;
之后x=g(g(n)),则可算出g(n)的循环节，在算出n的循环节就可以了！！
代码如下：
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<iomanip> 5 #include<cmath> 6 #include<cstring> 7 #include<vector> 8 #define ll __int64 9 #define mod1 1000000007 10 #define mod2 222222224 11 #define mod3 183120 12 #define mod4 240 13 using namespace std; 14 struct ma 15 { 16 ll a[2][2]; 17 }; 18 ma mul(ma aa,ma ab,ll mod) 19 { 20 ma ans; 21 for(int i=0;i<2;i++) 22 for(int j=0;j<2;j++){ 23 ans.a[i][j]=0; 24 for(int k=0;k<2;k++) 25 ans.a[i][j]=(ans.a[i][j]+aa.a[i][k]*ab.a[k][j])%mod; 26 } 27 return ans; 28 } 29 ma pows(ma aa,ll b,ll mod) 30 { 31 ma ans; 32 ans.a[0][0]=ans.a[1][1]=1; 33 ans.a[1][0]=ans.a[0][1]=0; 34 while(b){ 35 if(b&1) ans=mul(ans,aa,mod); 36 b>>=1; 37 aa=mul(aa,aa,mod); 38 } 39 return ans; 40 } 41 int main(){ 42 ll n; 43 ma p; 44 p.a[0][0]=3;p.a[0][1]=p.a[1][0]=1;p.a[1][1]=0; 45 while(cin>>n){ 46 ma ans; 47 if(n==0){ 48 printf("0 "); 49 continue; 50 } 51 ans=pows(p,n%mod4,mod3); 52 ans=pows(p,ans.a[1][0],mod2); 53 ans=pows(p,ans.a[1][0],mod1); 54 printf("%I64d ",ans.a[1][0]); 55 } 56 return 0; 57 }