hdu 1063 Exponentiation（高精度幂）

poj这题数据很水很容易过，然而hdu的这题可能是因为case太多O(125*125*n)的复杂度TLE，最后用了快速幂的方法优化到O（125*125*logn）过了。
140MS。
View Code
  1 /*
  2 Author:Zhaofa Fang
  3 Lang:C++
  4 */
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <sstream>
  8 #include <iostream>
  9 #include <cmath>
 10 #include <cstring>
 11 #include <algorithm>
 12 #include <string>
 13 #include <utility>
 14 #include <vector>
 15 #include <queue>
 16 #include <stack>
 17 #include <map>
 18 #include <set>
 19 using namespace std;
 20 
 21 typedef long long ll;
 22 #define DEBUG(x) cout<< #x << ':' << x << endl
 23 #define REP(i,n) for(int i=0;i < (n);i++)
 24 #define FOR(i,s,t) for(int i = (s);i <= (t);i++)
 25 #define PII pair<int,int>
 26 #define PB push_back
 27 #define MP make_pair
 28 #define ft first
 29 #define sd second
 30 #define lowbit(x) (x&(-x))
 31 #define INF (1<<30)
 32 
 33 
 34 
 35 void product(int a[],int b[],int c[])
 36 {
 37     REP(j,125)c[j]=0;
 38     int e = 0;
 39     int N = 125-1;
 40     while(N>=0 && !b[N] )N--;
 41     REP(k,N+1)
 42     {
 43         for(int j=0;j+k<125;j++)
 44         {
 45             int tmp = a[j] * b[k];
 46             int tmp1 = tmp + c[j+k] + e;
 47             c[j+k] = (tmp1)%10;
 48             e = (tmp1)/10;
 49         }
 50     }
 51     REP(k,125)b[k] = c[k];
 52 }
 53 void print(int b[],int num)
 54 {
 55     int k = 125 - 1,j=0;
 56     int end = 0;
 57     while(k>=0 && !b[k] )k--;
 58     while(end<num && !b[end])end++;
 59     k = max(num-1,k);
 60     //DEBUG(k);DEBUG(num);DEBUG(end);
 61     //puts("**********************************");
 62     for(int i=k;i>=end;i--)
 63     {
 64         j++;
 65         if(j == k-num+2)printf(".");
 66         printf("%d",b[i]);
 67     }
 68     if(end>k)printf("0");
 69     puts("");
 70 }
 71 void POW(int a[],int n,int num)
 72 {
 73     int b[125],c[125];
 74     REP(i,125)b[i] = a[i];
 75     while(n)
 76     {
 77         if(n & 1)
 78         {
 79             product(a,b,c);
 80             REP(i,125)b[i] = c[i];
 81         }
 82         n >>= 1;
 83         product(a,a,c);
 84         REP(i,125)a[i] = c[i];
 85     }
 86     print(b,num);
 87 }
 88 
 89 int main()
 90 {
 91     //freopen("in","r",stdin);
 92     char str[102];
 93     int a[125];
 94     int n;
 95     while(scanf("%s%d",str,&n)!=EOF)
 96     {
 97         int len = strlen(str);
 98         int num = 0;
 99         memset(a,0,sizeof(a));
100         for(int i=len-1,j=0;i>=0;j++,i--)
101         {
102             if(str[i] == '.')
103             {
104                 num = j;j--;
105             }
106             else
107             {
108                 a[j] = str[i] - '0';
109             }
110         }
111         num *= n;
112         POW(a,n-1,num);
113 
114     }
115     return 0;
116 }