// 0ms, 100%
// 8.8MB, 5.11%

class Solution {
public:
    double ePow(double x, int n, map<int,double> &m) {
        double h = 0;
        if (m.end() == m.find(n/2)) {
            h = m[n/2] = ePow(x, n/2, m);
        } else {
            h = m[n/2];
        }

        if (isinf(h)) return INFINITY;
        if (0 == n%2) return h*h;
        if (0 < n) return h*h*x;
        return h*h/x;
    }
    double myPow(double x, int n) {
        if (n == 0 || x == 1 || (x == -1 && n%2 == 0)) return 1;
        if (x == -1) return -1;
        if (n == 1) return x;
        if (n == -1) return 1.0/x;

        map <int, double> m;
        m[1] = x;
        m[-1] = 1.0/x;
        return ePow(x, n, m);
    }
};