poj 2748這道題跟
Fibonacci在解法上一樣，不過這道題特殊的地方在于測試數(shù)據(jù)非常多，用普通的做法(t*log200000000)會超時。
推導(dǎo)到這一步：f[i]=3*f[i-1]-f[i-2]，其中f[i]是輸入i時的解。
最樸素的辦法就是對每個i都從0開始遞推。這樣最壞復(fù)雜度是O(t*200000000)。
改進(jìn)的辦法是，將遞推式寫成矩陣相乘的式子，具體見
借助矩陣快速計算總結(jié)與。
代碼還是比較簡單的：
1 // 2748 matrix formula
2
3 #include <iostream>
4
5 using namespace std;
6
7 int first[2]={1,1};
8 int trans[2][2]={{3,-1},{1,0}};
9 __int64 tmp[31][2][2];
10 __int64 p[31];
11 int e[31];
12 int a[10000000];
13
14 void init()
15 {
16 p[0]=1;
17 int i,j;
18 for(i=1;i<=30;i++) p[i]=2*p[i-1];
19 tmp[0][0][0]=3,tmp[0][0][1]=-1,tmp[0][1][0]=1,tmp[0][1][1]=0;
20 for(i=1;i<=30;i++){
21 tmp[i][0][0]=(tmp[i-1][0][0]*tmp[i-1][0][0]+tmp[i-1][0][1]*tmp[i-1][1][0])%100000;
22 tmp[i][0][1]=(tmp[i-1][0][0]*tmp[i-1][0][1]+tmp[i-1][0][1]*tmp[i-1][1][1])%100000;
23 tmp[i][1][0]=(tmp[i-1][1][0]*tmp[i-1][0][0]+tmp[i-1][1][1]*tmp[i-1][1][0])%100000;
24 tmp[i][1][1]=(tmp[i-1][1][0]*tmp[i-1][0][1]+tmp[i-1][1][1]*tmp[i-1][1][1])%100000;
25 }
26 a[0]=1;
27 a[1]=1;
28 for(i=2;i<10000000;i++){
29 a[i]=(3*a[i-1]-a[i-2]+200000)%100000;
30 }
31 }
32
33 int solve(int n)
34 {
35 memset(e,0,sizeof(e));
36 int nn=n;
37 int i=0;
38 while(nn!=0){
39 int x=nn%2;
40 nn/=2;
41 e[i++]=x;
42 }
43 __int64 res[2][2]={{1,0},{0,1}},t[2][2];
44
45 for(i=0;i<=30;i++){
46 if(e[i]){
47 t[0][0]=res[0][0]*tmp[i][0][0]+res[0][1]*tmp[i][1][0];
48 t[0][1]=res[0][0]*tmp[i][0][1]+res[0][1]*tmp[i][1][1];
49 t[1][0]=res[1][0]*tmp[i][0][0]+res[1][1]*tmp[i][1][0];
50 t[1][1]=res[1][0]*tmp[i][0][1]+res[1][1]*tmp[i][1][1];
51 res[0][0]=t[0][0]%100000,res[0][1]=t[0][1]%100000,res[1][0]=t[1][0]%100000,res[1][1]=t[1][1]%100000;
52 }
53 }
54
55 int ans=(res[0][0]+res[0][1]+200000)%100000;
56 printf("%d\n",ans);
57 return ans;
58 }
59
60 int main()
61 {
62 //printf("%d\n",(-11)%10);
63 init();
64 int t,n;
65 /*
66 scanf("%d",&t);
67 while(t--){
68 scanf("%d",&n);
69 if(n<10000000) printf("%d\n",a[n]);
70 else solve(n-1);
71 }
72 */
73 int x,y;
74 for(int i=2;i<2000000000;i++){
75 if(i<10000000) {x=y,y=a[i];}
76 else {x=y;y=solve(i-1);}
77 if(x==1 && y==1){printf("period=%d\n",i);break;}
78 }
79 return 1;
80 }
最后還是看了discuss里的解法，f[i]其實是以75000為循環(huán)節(jié)：f[75000]=f[0]，f[75001]=f[1]且f是2階的遞推式。編程算出前10000000個數(shù)，然后逐個枚舉就能找出循環(huán)節(jié)。
這道題給我影響深刻的地方在于可以找循環(huán)節(jié)。
代碼非常簡單：
1 // 2748 matrix formula
2
3 #include <iostream>
4
5 using namespace std;
6
7 int a[75000];
8
9 void init()
10 {
11 a[0]=1;
12 a[1]=1;
13 for(int i=2;i<75000;i++){
14 a[i]=(3*a[i-1]-a[i-2]+200000)%100000;
15 }
16 }
17 int main()
18 {
19 init();
20 __int64 t,n;
21 scanf("%I64d",&t);
22 while(t--){
23 scanf("%I64d",&n);
24 if(n<75000) printf("%d\n",a[n]);
25 else printf("%d\n",a[n%75000]);
26 }
27 return 1;
28 }