Hat's Fibonacci（大数加法+直接暴力）

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1250

hdu1250：

Hat's Fibonacci

Problem Description

Input

Each line will contain an integers. Process to end of file.

Output

For each case, output the result in a line.

Sample Input

Sample Output

4203968145672990846840663646 Note: No generated Fibonacci number in excess of 2005 digits will be in the test data, ie. F(20) = 66526 has 5 digits.

Author

戴帽子的

题解，同一般的斐波那契数列来说，最先的我想到了用大数加法和快速幂矩阵的方法来做，但是由于大数乘法的模板是O(n^2)所以超时了，所以考虑只用大数加法的直接暴力方法，由于斐波那契数列增长很快，所以位数不超过2005的前提下最多n 不超过10000,然后就过了， 希望看到的大神吗也可以帮我提供一个复杂度小的大数乘法的模板，万分感激 

下面给出ac代码，和用矩阵快速幂tle的代码：

ac代码：

 1 #include <iostream>  2 #include<cstdio>  3 #include<string>  4 #include<cstring>  5 #include<algorithm>  6 using namespace std;  7 string add(string s1,string s2)        8 {  9       string ans = ""; 10       int i,j,x,y,k=0; 11       for(i=s1.length()-1,j=s2.length()-1;i>=0 && j>=0 ;i--,j--) 12       { 13          x = s1[i] - '0'; 14          y = s2[j] - '0'; 15          ans += char((x+y+k)%10 + '0'); 16          k = (x+y+k)/10; 17       } 18       while(i>=0) 19       { 20          x=s1[i]-'0'; 21          ans += char ((x+k)%10 + '0'); 22          k = (x+k)/10; 23          i--; 24       } 25       while(j>=0) 26       { 27          y=s2[j]-'0'; 28          ans += char((y+k)%10 + '0'); 29          k = (y+k)/10; 30          j--; 31       } 32       if(k>0) 33       ans += '1'; 34       //ans.reverse(); 35       reverse(ans.begin(),ans.end()); 36       return ans; 37 } 38 string ms1, ms2, ms3, ms4, ms; 39 int main() 40 { 41     int n; 42     while(~scanf("%d",&n)) 43     { 44         ms1 = ms2 = ms3 = ms4 = "1"; 45         if(n <= 4) {puts("1"); continue;} 46         for(int i = 0; i < n-4; i++) 47         { 48             ms = add(ms1, ms2); 49             ms = add(ms, ms3); 50             ms = add(ms, ms4); 51             ms1 = ms2; 52             ms2 = ms3; 53             ms3 = ms4; 54              ms4 = ms; 55         } 56         cout << ms << endl; 57   } 58      return 0; 59 }

矩阵快速幂tle代码：

  1 #include <iostream>   2 #include<cstdio>   3 #include<string>   4 #include<cstring>   5 #include<algorithm>   6 using namespace std;   7 string add(string s1,string s2)         8 {   9       string ans = "";  10       int i,j,x,y,k=0;  11       for(i=s1.length()-1,j=s2.length()-1;i>=0 && j>=0 ;i--,j--)  12       {  13          x = s1[i] - '0';  14          y = s2[j] - '0';  15          ans += char((x+y+k)%10 + '0');  16          k = (x+y+k)/10;  17       }  18       while(i>=0)  19       {  20          x=s1[i]-'0';  21          ans += char ((x+k)%10 + '0');  22          k = (x+k)/10;  23          i--;  24       }  25       while(j>=0)  26       {  27          y=s2[j]-'0';  28          ans += char((y+k)%10 + '0');  29          k = (y+k)/10;  30          j--;  31       }  32       if(k>0)  33       ans += '1';  34       //ans.reverse();  35       reverse(ans.begin(),ans.end());  36       return ans;  37 }  38 string mul(string s1,string s2)  39 {     40     string ans = "";  41     int c = 0;  42     for(int i = s1.length()-1; i >= 0; i--)  43     {  44         //计算s1[i]*s2,结果保存在tem中   45         string tem = "";  46         int x = s1[i] - '0',k = 0;//乘数和初始余数   47         for(int j = s2.length()-1; j >= 0; j--)  48         {  49             int y = s2[j] - '0';  50             int d = x*y+k;   51             tem = char(d%10 + '0') + tem;  52             k = d/10;  53         }  54         if(k)  55         tem = char(k+'0') + tem;  56         for(int h = 0; h < c; h++)  57            tem = tem+'0';  58         c++;  59         //tem计算完毕   60         ans = add(ans,tem);  61     }  62     return ans;  63 }  64 struct mlt{  65     string a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,d1,d2,d3,d4;  66     void out (){  67         printf("%s %s %s %s/n", a1.c_str(), a2.c_str(), a3.c_str(), a4.c_str());  68         printf("%s %s %s %s/n", b1.c_str(), b2.c_str(), b3.c_str(), b4.c_str());  69         printf("%s %s %s %s/n", c1.c_str(), c2.c_str(), c3.c_str(), c4.c_str());  70         printf("%s %s %s %s/n", d1.c_str(), d2.c_str(), d3.c_str(), d4.c_str());  71     }  72     mlt operator * (const mlt m) const  73     {  74         mlt tm;  75         tm.a1 = add(add(add(mul(a1,m.a1),mul(a2,m.b1)),mul(a3,m.c1)),mul(a4,m.d1));      76         tm.a2 = add(add(add(mul(a1,m.a2),mul(a2,m.b2)),mul(a3,m.c2)),mul(a4,m.d2));  77         tm.a3 = add(add(add(mul(a1,m.a3),mul(a2,m.b3)),mul(a3,m.c3)),mul(a4,m.d3));  78         tm.a4 = add(add(add(mul(a1,m.a4),mul(a2,m.b4)),mul(a3,m.c4)),mul(a4,m.d4));  79         tm.b1 = add(add(add(mul(b1,m.a1),mul(b2,m.b1)),mul(b3,m.c1)),mul(b4,m.d1));      80         tm.b2 = add(add(add(mul(b1,m.a2),mul(b2,m.b2)),mul(b3,m.c2)),mul(b4,m.d2));  81         tm.b3 = add(add(add(mul(b1,m.a3),mul(b2,m.b3)),mul(b3,m.c3)),mul(b4,m.d3));  82         tm.b4 = add(add(add(mul(b1,m.a4),mul(b2,m.b4)),mul(b3,m.c4)),mul(b4,m.d4));  83         tm.c1 = add(add(add(mul(c1,m.a1),mul(c2,m.b1)),mul(c3,m.c1)),mul(c4,m.d1));      84         tm.c2 = add(add(add(mul(c1,m.a2),mul(c2,m.b2)),mul(c3,m.c2)),mul(c4,m.d2));  85         tm.c3 = add(add(add(mul(c1,m.a3),mul(c2,m.b3)),mul(c3,m.c3)),mul(c4,m.d3));  86         tm.c4 = add(add(add(mul(c1,m.a4),mul(c2,m.b4)),mul(c3,m.c4)),mul(c4,m.d4));  87         tm.d1 = add(add(add(mul(d1,m.a1),mul(d2,m.b1)),mul(d3,m.c1)),mul(d4,m.d1));      88         tm.d2 = add(add(add(mul(d1,m.a2),mul(d2,m.b2)),mul(d3,m.c2)),mul(d4,m.d2));  89         tm.d3 = add(add(add(mul(d1,m.a3),mul(d2,m.b3)),mul(d3,m.c3)),mul(d4,m.d3));  90         tm.d4 = add(add(add(mul(d1,m.a4),mul(d2,m.b4)),mul(d3,m.c4)),mul(d4,m.d4));      91     return tm;  92     }  93 };  94 string qkmul(int n)  95 {  96     mlt flag;  97     flag.a1 = flag.a2 = flag.a3 = flag.a4 = flag.b1 = flag.c2 = flag.d3 ="1";  98     flag.b2 = flag.b3 = flag.b4 = flag.c1 = flag.c3 = flag.c4 = flag.d1 = flag.d2 = flag.d4 = "0" ;  99     n = n-4; 100     mlt ret; ret.a1 = ret.b2 = ret.c3 = ret.d4 = "1"; 101     ret.a2 = ret.a3 = ret.a4 = ret.b1 = ret.b3 = ret.b4 = ret.c1 = ret.c2 = ret.c4 = ret.d1 = ret.d2 = ret.d3 = "0"; 102     while(n!=0) 103     { 104         if(n%2==1) 105             ret = ret*flag; 106         n/=2; 107         flag = flag*flag; 108     } 109     //flag.out(); 110     flag = ret; 111     string ss = ""; 112     ss = add(add(add(flag.a1,flag.a2),flag.a3),flag.a4); 113     return ss; 114 } 115  116 int main() 117 { 118     int n; 119     while(~scanf("%d",&n)) 120     { 121         string sss = qkmul(n); 122         cout<<sss<<endl; 123      } 124      return 0; 125 }

注明： 一般的斐波那契在n不是很大的情况可以直接用暴力的方法就可以解决了。