# A Short problem

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1716    Accepted Submission(s): 631

Problem Description

According to a research, VIM users tend to have shorter fingers, compared with Emacs users. 　　Hence they prefer problems short, too. Here is a short one: 　　Given n (1 <= n <= 1018), You should solve for g(g(g(n))) mod 109 + 7 　　where g(n) = 3g(n - 1) + g(n - 2) g(1) = 1 g(0) = 0

Input

There are several test cases. For each test case there is an integer n in a single line. 　　Please process until EOF (End Of File).

Output

For each test case, please print a single line with a integer, the corresponding answer to this case.

Sample Input

0 1 2

Sample Output

0 1 42837

Source

``` 1 /*采用事先处理自己可以求出来*/
2 LL work(LL mod){
3   LL a=0,b=1;
4     for(LL i=2;;++i)
5     {
6       a=(b*3+a)%mod;
7         a=a^b;
8         b=a^b;
9         a=a^b;
10         if(a == 0 && b == 1)  return i;
11  }```

``` 1 //#define LOCAL
2 #include<iostream>
3 #include<cstdio>
4 #include<cstring>
5 #define LL __int64
6 using namespace std;
7 const int mod1 =1000000007;
8 const int mod2=222222224;
9 const int mod3=183120;
10
11 LL mat[2][2];
12 LL ans[2][2];
13 LL n;
14
15 void Matrix(LL a[][2],LL b[][2],LL mod)
16 {
17     LL cc[2][2]={0};
18     for(int i=0;i<2;i++)
19     {
20       for(int j=0;j<2;j++)
21       {
22           for(int k=0;k<2;k++)
23         {
24             cc[i][j]=(cc[i][j]+a[i][k]*b[k][j])%mod;
25         }
26       }
27     }
28     for(int i=0;i<2;i++)
29     {
30       for(int j=0;j<2;j++)
31       {
32           a[i][j]=cc[i][j];
33       }
34     }
35 }
36
37 void pow(LL w,LL mod)
38 {
39   while(w>0)
40   {
41     if(w&1) Matrix(ans,mat,mod);
42      w>>=1;
43      if(w==0)break;
44      Matrix(mat,mat,mod);
45   }
46 }
47 void input(LL w,LL mod)
48 {
49      mat[0][0]=3;
50      mat[0][1]=mat[1][0]=1;
51      mat[1][1]=0;
52      ans[0][0]=ans[1][1]=1;
53      ans[0][1]=ans[1][0]=0;
54      pow(w,mod);
55 //     printf("%I64d\n",ans[0][0]);
56 }
57 void work(int i,__int64 w)
58 {
59   if(i==4||w==0||w==1)
60   {
61       if(w==0)
62          printf("0\n");
63       else if(w==1)
64           printf("1\n");
65       else
66       printf("%I64d\n",ans[0][0]);
67       return ;
68   }
69   LL mod;
70   if(i==1)mod=mod3;
71   else if(i==2)mod=mod2;
72   else if(i==3)mod=mod1;
73   input(w-1,mod);
74   work(i+1,ans[0][0]);
75 }
76 int main()
77 {
78   #ifdef LOCAL
79    freopen("test.in","r",stdin);
80   #endif
81   while(scanf("%I64d",&n)!=EOF)
82      work(1,n);
83  return 0;
84 }```

0 条评论

## 相关文章

332130

### ZOJ 80ers' Memory

80ers' Memory ---- Time Limit: 1 Second      Memory Limit: 32768 KB ---- I guess...

30560

### HDUOJ-------Naive and Silly Muggles

Naive and Silly Muggles Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: ...

33360

### HDUOJ----Good Numbers

Good Numbers Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768...

31160

Holding Bin-Laden Captive! Time Limit: 2000/1000 MS (Java/Others)    Memory Limi...

283110

### HDUOJ----（1031）Design T-Shirt

Design T-Shirt Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/327...

373130

### poj-------(2240)Arbitrage(最短路)

Arbitrage Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 156...

38080

### HDUOJ------2492Ping pong

Ping pong Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ...

33870

### poj 1915 Knight Moves

Knight Moves Time Limit: 1000MS Memory Limit: 30000K Total Submissions:...

21630

### hdu 1695 GCD（莫比乌斯反演）

GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

41060