HDU4291 A Short problem

 1 #include <map>
 2 #include <iostream>
 3 #define ll long long
 4 using namespace std;
 5 const int MOD = 1000000007;
 6 struct node{
 7     long long a1,a2,a3,a4;
 8     node(){}
 9     node(ll a,ll b,ll c,ll d){a1=a;a2=b;a3=c;a4=d;}
10 };
11 node gn=node(0,1,1,3);
12 node org=node(0,1,1,3);
13 node dw=node(1,0,0,1);
14 node mult(node a,node b,int mod)
15 {
16     node ans;
17     ans.a1=(a.a1*b.a1+a.a2*b.a3)%mod;
18     ans.a2=(a.a1*b.a2+a.a2*b.a4)%mod;
19     ans.a3=(a.a3*b.a1+a.a4*b.a3)%mod;
20     ans.a4=(a.a3*b.a2+a.a4*b.a4)%mod;
21     return ans;
22 }
23 node g(long long n,long long mod)
24 {
25     node ans;
26     if(n==0) return dw;
27     ans=g(n/2,mod);
28     ans=mult(ans,ans,mod);
29     if(n&1) ans=mult(ans,org,mod);
30     return ans;
31 }
32 ll calcu(int mod)//求周期用的
33 {
34     map<ll,ll> m;
35     for(int i=0;i<10000;i++)
36         m[g(i,mod).a3]=i;
37     for(int i=10000;1;i+=10000)
38     {
39         node t=g(i,mod);
40         if(m[t.a3])
41         {
42             int ans=i-m[t.a3];
43             if(m[g(ans,mod).a3]==0) return ans;
44         }
45         m[t.a3]=i;
46     }
47 }
48 int main()
49 {
50     ll n;
51     int ans;
52     int mod1=222222224;
53     int mod2=183120;
54     while(cin>>n)
55     {
56         ans=g(n,mod2).a3;
57         ans=g(ans,mod1).a3;
58         ans=g(ans,MOD).a3;
59         cout<<ans<<endl;
60     }
61     return 0;
62 }