HDU----(4291)A Short problem(快速矩阵幂)
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
2012 ACM/ICPC Asia Regional Chengdu Online
此题出得比较精妙，
分析:假设g(g(g(n)))=g(x),x可能超出范围,但是由于mod 10^9+7,所以可以求出x的循环节
求出x的循环节后,假设g(g(g(n)))=g(x)=g(g(y)),即x=g(y),y也可能非常大,但是由x的循环节可以求出y的循环节
如何求循环节点：
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 }所以依次将mod1带入得到mod2=222222224;
然后将mod2带入得到mod3=183120;
然后就是快速矩阵了。
代码：
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 }