#1392 (C++11) No.53 悪の漸化式

• 問題: No.53 悪の漸化式
• ユーザー: sune232002
• 提出日時: 2014-11-01 15:02:08
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 31 ms / 5,000 ms
• コード長: 11,361 bytes
• コンパイル時間: 2,044 ms
• コンパイル使用メモリ: 190,552 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-09 18:35:04
• 合計ジャッジ時間: 2,819 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	3 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	3 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	3 ms; 5,376 KB
testcase_12	AC	5 ms; 5,376 KB
testcase_13	AC	7 ms; 5,376 KB
testcase_14	AC	9 ms; 5,376 KB
testcase_15	AC	11 ms; 5,376 KB
testcase_16	AC	15 ms; 5,376 KB
testcase_17	AC	20 ms; 5,376 KB
testcase_18	AC	25 ms; 5,376 KB
testcase_19	AC	31 ms; 5,376 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T>ostream&operator<<(ostream &o,const vector<T>&t){o<<'[';FOR(i,t){if(i!=t.begin())o<<',';o<<*i;}return o<<']';}
template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';}
template<int N,class Tp>void output(ostream&,const Tp&){}
template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);}
template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';}
template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20];
int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);}
template<class T>void outputs(T t){output(t);}
template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);}
template<class T>void output(T *a,int n){REP(i,n)output(a[i],i!=n-1?',':10);}
template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);}
template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;);
if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;}
template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);}
template<class T>bool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;}

template<class T>
T gcd(T a, T b) {
  if (a <= 0) return b;
  return gcd(b % a, a);
}

template<class T>
struct Rational {
  T p, q;
  Rational(T p = 0, T q = 1) : p(p), q(q) { normalize(); }
  void normalize() {
    if (q < 0) { p=-p;q=-q; }
    T d = gcd(abs(p), q);
    if (d == 0) p = 0, q = 1;
    else p /= d, q /= d;
  }
  Rational inv() { return Rational(q, p); }
  Rational &operator-() { p *= -1; return *this; }
  Rational operator-() const { return Rational(-p, q); }
  Rational operator+(const Rational &rhs) const { return Rational(p * rhs.q + rhs.p * q, q * rhs.q); }
  Rational operator-(const Rational &rhs) const { return Rational(p * rhs.q - rhs.p * q, q * rhs.q); }
  Rational operator*(const Rational &rhs) const { return Rational(p * rhs.p, q * rhs.q); }
  Rational operator/(const Rational &rhs) const { return Rational(p * rhs.q, q * rhs.p);}
  Rational &operator+=(const Rational &rhs) { *this = *this + rhs; return *this; }
  Rational &operator-=(const Rational &rhs) { *this = *this - rhs; return *this; }
  Rational &operator*=(const Rational &rhs) { *this = *this * rhs; return *this; }
  Rational &operator/=(const Rational &rhs) { *this = *this / rhs; return *this; }
  bool operator<(const Rational &rhs) const { return p * rhs.q < rhs.p * q; }
  bool operator>(const Rational &rhs) const { return p * rhs.q > rhs.p * q; }
  bool operator<=(const Rational &rhs) const { return p * rhs.q <= rhs.p * q; }
  bool operator>=(const Rational &rhs) const { return p * rhs.q >= rhs.p * q; }
  bool operator!=(const Rational &rhs) const { return p * rhs.q != rhs.p * q; }
  bool operator==(const Rational &rhs) const { return p * rhs.q == rhs.p * q; }
  string to_f(int digit) const {
    stringstream ss;
    T t = p;
    REP(i,digit+1) {
      ss << t/q;
      if (!i) ss << '.';
      t = t%q*10;
    }
    return ss.str();
  }
  friend Rational gcd(const Rational &a, const Rational &b) {
    T lcm = a.q*b.q / gcd(a.q, b.q);
    T p1 = a.p * lcm / a.q;
    T p2 = b.p * lcm / b.q;
    return Rational(gcd(p1, p2), lcm);
  }
  friend Rational abs(const Rational &rhs) {
    return Rational(abs(rhs.p), rhs.q);
  }
  friend ostream &operator<<(ostream &os, const Rational &rhs) {
    os << '(' << rhs.p << "/" << rhs.q << ')';
    return os;
  }
};

struct Long {
  static const long long BASE = 10000;
  static const int BW = 4;
  vector<long long> digits;
  Long(long long a = 0) {
    digits.push_back(a);
    Normalize();
  }
  Long(const string &str) {
    if (str.length() == 0) {
      digits.push_back(0);
    } else {
      int s = str[0] != '-' ? 1 : -1;
      int sw = s == -1 ? 1 : 0;
      digits = vector<long long>((str.size() - 1 - sw) / BW + 1);
      int i = (str.size() - sw) % BW;
      int index = digits.size() - 1;
      if (i > 0) { i -= BW; }
      for (; i < (int)str.size() - sw; i+= BW) {
        long long a = 0;
        for (int j = 0; j < BW; j++) {
          a = 10 * a + (i + j + sw >= sw ? str[i + j + sw] - '0' : 0);
        }
        digits[index--] = a * s;
      }
    }
    Normalize();
  }
  void resize(int s) { digits.resize(s); }
  int size() const { return digits.size(); } // size of vector of digits
  int size2() const {           // number of digits
    return abs().toString().size();
  }
  int sign() const { return digits[digits.size() - 1] > 0 ? 1 : (digits[digits.size() - 1] < 0 ? -1 : 0); }
  string toString() const {
    int s = sign();
    ostringstream os;
    os << digits[size() - 1];
    for (int i = size() - 2; i >= 0; i--)
      os << setw(Long::BW) << setfill('0') << digits[i] * s;
    return os.str();
  }
  Long abs() const {
    Long ret = *this;
    return ret.sign() >= 0 ? ret : -ret;;
  }
  long long operator[](int index) const { return digits[index]; }
  long long &operator[](int index) { return digits[index]; }
  bool operator<(const Long &rhs) const {
    const Long &lhs = *this;
    if (lhs.sign() != rhs.sign()) { return lhs.sign() < rhs.sign(); }
    if (lhs.size() != rhs.size()) { return lhs.sign() > 0 ? lhs.size() < rhs.size() : lhs.size() > rhs.size(); }
    for (int i = lhs.size() - 1; i >= 0; i--) {
      if (lhs[i] != rhs[i]) { return lhs[i] < rhs[i]; }
    }
    return false;
  }
  bool operator>(const Long &rhs) const { return rhs < *this; }
  bool operator<=(const Long &rhs) const { return !(rhs < *this); }
  bool operator>=(const Long &rhs) const { return !(*this < rhs); }
  bool operator!=(const Long &rhs) const { return *this < rhs || rhs < *this; }
  bool operator==(const Long &rhs) const { return !(*this < rhs) && !(rhs < *this); }

  Long &Normalize() {
    int s = 1;
    while (digits[size() - 1] <= -BASE) {
      ll v = digits[size() - 1] / BASE;
      digits.push_back(v);
      digits[size() - 2] -= v * BASE;
    }
    for (int i = 0; i < size(); i++) {
      if (i == size() - 1 && digits[i] < 0) {
        goto minus;
      } else if (digits[i] < 0) {
        long long a = -((digits[i] + 1) / BASE) + 1;
        digits[i] = a * BASE + digits[i];
        digits[i + 1] -= a;
      } else if (digits[i] >= BASE) {
        if (i == size() - 1) { digits.push_back(0); }
        long long a = digits[i] / BASE;
        digits[i] = digits[i] % BASE;
        digits[i + 1] += a;
      }
      assert(0 <= digits[i] && digits[i] < BASE);
      if (digits[i] != 0) { s = i + 1; }
    }
    assert(0 <= digits[s - 1] && digits[s - 1] < BASE);
    assert(s == 1 || digits[s - 1] != 0);
    resize(s);
    return *this;
minus:
    s = 1;
    for (int i = size() - 2; i >= 0; i--) {
      digits[i + 1] += 1;
      digits[i] -= BASE;
      if (digits[i + 1] != 0) { s = max(s, i + 2); }
      assert(digits[i + 1] <= 0);
      assert(digits[i] <= 0);
    }
    resize(s);
    return *this;
  }
  Long operator+(const Long &rhs) const {
    Long ret = *this;
    if (ret.size() < rhs.size()) { ret.resize(rhs.size()); }
    for (int i = 0; i < rhs.size(); i++) { ret[i] += rhs[i]; }
    return ret.Normalize();
  }
  Long operator-(const Long &rhs) const {
    //assert(*this >= rhs);
    Long ret = *this;
    if (ret.size() < rhs.size()) { ret.resize(rhs.size()); }
    for (int i = 0; i < rhs.size(); i++) { ret[i] -= rhs[i]; }
    return ret.Normalize();
  }
  Long operator*(const Long &rhs) const {
    const Long &lhs = *this;
    Long ret;
    ret.resize(this->size() + rhs.size());
    for (int i = 0; i < lhs.size(); i++) {
      for (int j = 0; j < rhs.size(); j++) {
        ret[i + j] += lhs[i] * rhs[j];
      }
    }
    return ret.Normalize();
  }
  Long operator/(const Long &rhs) const {
    return this->divmod(rhs).first;
  }
  Long operator%(const Long &rhs) const {
    return this->divmod(rhs).second;
  }
  Long operator-() const {
    return *this * -1;
  }
  Long &operator+=(const Long &rhs) {
    return *this = *this + rhs;
  }
  Long &operator-=(const Long &rhs) {
    return *this = *this - rhs;
  }
  Long &operator*=(const Long &rhs) {
    return *this = *this * rhs;
  }
  Long &operator/=(const Long &rhs) {
    return *this = *this / rhs;
  }
  Long &operator/=(long long rhs) {
    return *this = *this / rhs;
  }
  Long &operator%=(const Long &rhs) {
    return *this = *this % rhs;
  }
  pair<Long, long long> divmodll(long long rhs) const {
    Long ret = *this;
    long long c = 0;
    long long t;
    for (int i = ret.size() - 1; i >= 0; i--) {
      t = BASE * c + ret[i];
      ret[i] = t / rhs;
      c = t % rhs;
    }
    return make_pair(ret.Normalize(), c);
  }
  pair<Long, Long> divmod(Long rhs) const {
    Long lhs = *this;
    if (lhs.size() < rhs.size()) { return pair<Long, Long>(0, lhs); }
    int s = lhs.sign() * rhs.sign();
    lhs = lhs.abs(); rhs = rhs.abs();
    long long F = BASE / (rhs[rhs.size() - 1] + 1);  // multiplying good-factor
    lhs = lhs * F; rhs = rhs * F;
    Long ret;
    ret.resize(lhs.size() - rhs.size() + 1);
    for (int k = ret.size() - 1, i = lhs.size() - 1; k >= 0; k--, i--) {
      ret[k] = (i + 1 < lhs.size() ? lhs[i + 1] : 0) * BASE + (i < lhs.size() ? lhs[i] : 0);
      ret[k] /= rhs[rhs.size() - 1];
      Long t;
      t.resize(k + rhs.size());
      for (int m = 0; m < rhs.size(); m++) {
        t[k + m] = ret[k] * rhs[m];
      }
      t.Normalize();
      while (lhs < t) {
        ret[k] -= 1;
        for (int m = 0; m < rhs.size(); m++) {
          t[k + m] -= rhs[m];
        }
        t.Normalize();
      }
      lhs = lhs - t;
    }
    return make_pair(ret.Normalize() * s, lhs.divmodll(F).first * s);
  }
  Long pow(ll n) {
    Long A(*this);
    Long B(1);
    while(n) {
      if (n&1) B *= A;
      A *= A;
      n >>= 1;
    }
    return B;
  }
};

ostream &operator<<(ostream &os, const Long &rhs) {
  os << rhs.toString();
  return os;
}
istream &operator>>(istream &is, Long &rhs) {
  string s;
  is >> s;
  rhs = Long(s);
  return is;
}
Long abs(const Long &x) {
  return x<0?-x:x;
}

typedef Rational<Long> Rat;

Rat a[101], b[101];

int main() {
  int n;
  while(input(n)) {
    a[0] = Long(4);
    a[1] = Long(3);
    for (int i=2; i<=n; ++i) a[i] = a[i-1]*Rat(19,4) - a[i-2]*Rat(3);
    cout << a[n].to_f(20) << endl;
  }
}