結果
問題 | No.53 悪の漸化式 |
ユーザー |
![]() |
提出日時 | 2018-04-20 16:11:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 7 ms / 5,000 ms |
コード長 | 20,689 bytes |
コンパイル時間 | 3,329 ms |
コンパイル使用メモリ | 203,628 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-27 05:06:27 |
合計ジャッジ時間 | 3,802 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include "bits/stdc++.h"using namespace std;typedef long long ll;typedef pair<int, int> pii;typedef pair<ll, ll> pll;const int INF = 1e9;const ll LINF = 1e18;template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out<< Mat[i];} return out; }template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out <<it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }/*<url:https://yukicoder.me/problems/no/53>問題文============================================================以下の漸化式で定義される数列 {Ak}∞k=0 の第 N 項 AN を求めるプログラムを書け。A0=4,A1=3,4Ak=19Ak−1−12Ak−2,k≥2.=================================================================解説=============================================================================================================================*/namespace arithmetic {template<typename T> class Addition {public:template<typename V> T operator+(const V& v) const {return T(static_cast<const T&>(*this)) += v;}};template<typename T> class Subtraction {public:template<typename V> T operator-(const V& v) const {return T(static_cast<const T&>(*this)) -= v;}};template<typename T> class Multiplication {public:template<typename V> T operator*(const V& v) const {return T(static_cast<const T&>(*this)) *= v;}};template<typename T> class Division {public:template<typename V> T operator/(const V& v) const {return T(static_cast<const T&>(*this)) /= v;}};template<typename T> class Modulus {public:template<typename V> T operator%(const V& v) const {return T(static_cast<const T&>(*this)) %= v;}};}template<typename T> class IndivisibleArithmetic : public arithmetic::Addition<T>, public arithmetic::Subtraction<T>, public arithmetic::Multiplication<T> {};template<typename T> class Arithmetic : public IndivisibleArithmetic<T>, public arithmetic::Division<T> {};template<typename T> class Ordered {public:template<typename V> bool operator==(const V& v) const {return !(static_cast<T>(v) < static_cast<const T&>(*this) || static_cast<const T&>(*this) < static_cast<T>(v));}template<typename V> bool operator!=(const V& v) const {return static_cast<T>(v) < static_cast<const T&>(*this) || static_cast<const T&>(*this) < static_cast<T>(v);}template<typename V> bool operator>(const V& v) const {return static_cast<T>(v) < static_cast<const T&>(*this);}template<typename V> bool operator<=(const V& v) const {return !(static_cast<T>(v) < static_cast<const T&>(*this));}template<typename V> bool operator>=(const V& v) const {return !(static_cast<const T&>(*this) < static_cast<T>(v));}};template<int IntegerSize = 6, int DecimalSize = 9>class BigDecimal : public Arithmetic<BigDecimal<IntegerSize, DecimalSize>>, public Ordered<BigDecimal<IntegerSize, DecimalSize>> {private:const static int BitSize = 31;const static bool PLUS = false;const static bool MINUS = true;constexpr static long double EPSILON = pow<long double>(2, -(BitSize - 4) * DecimalSize);bool sign;long long d[IntegerSize + DecimalSize];public:BigDecimal() {*this = BigDecimal(0);}BigDecimal(int n) {sign = PLUS;for (auto& i : d) i = 0;d[DecimalSize] = n;normal();}BigDecimal(long long n) {sign = PLUS;for (auto& i : d) i = 0;d[DecimalSize] = n;normal();}BigDecimal(string str) {*this = BigDecimal(0);bool minus = false;if (str[0] == '-') {minus = true;str = str.substr(1);}BigDecimal t = 1;bool decimal = false;for (int i = 0; i < (int)str.size(); ++i) {if (str[i] == '.') {decimal = true;} else {if (decimal) *this += (t /= 10) * (str[i] - '0');else *this = *this * 10 + (str[i] - '0');}}if (minus) sign = MINUS;}BigDecimal(double r) {*this = BigDecimal(0);int n;BigDecimal b = (r >= 0 ? BigDecimal(1) : BigDecimal(-1));r = 2 * abs(frexp(abs(r), &n));b <<= n - 1;while (r) {if (r >= 1) {*this += b;r -= 1;}r *= 2;b >>= 1;}}BigDecimal(long double r) {*this = BigDecimal(0);int n;BigDecimal b = (r >= 0 ? BigDecimal(1) : BigDecimal(-1));r = 2 * abs(frexp(abs(r), &n));b <<= n - 1;while (r) {if (r >= 1) {*this += b;r -= 1;}r *= 2;b >>= 1;}}BigDecimal normal() {for (int i = 0; i < IntegerSize + DecimalSize - 1; ++i) {d[i + 1] += d[i] >> BitSize;d[i] &= (1ll << BitSize) - 1;}if (d[IntegerSize + DecimalSize - 1] < 0) {sign = !sign;for (int i = 0; i < IntegerSize + DecimalSize; ++i) d[i] = -d[i];normal();}if (d[IntegerSize + DecimalSize - 1] >= (1ll << BitSize)) throw "overflow";for (int i = 0; i < IntegerSize + DecimalSize; ++i) if (d[i] != 0) {return *this;}sign = PLUS;return *this;}BigDecimal operator-() const {BigDecimal bd(*this);bd.sign = !bd.sign;return bd;}BigDecimal operator<<(int a) const {return BigDecimal(*this) <<= a;}BigDecimal operator>>(int a) const {return BigDecimal(*this) >>= a;}BigDecimal operator%(const BigDecimal &a) const {return BigDecimal(*this) %= a;}BigDecimal operator<<=(int a) {if (a < 0) return *this >>= -a;while (a >= BitSize) {if (d[IntegerSize + DecimalSize - 1]) throw "overflow";for (int i = IntegerSize + DecimalSize; --i > 0; ) d[i] = d[i - 1];d[0] = 0;a -= BitSize;}if (d[IntegerSize + DecimalSize - 1] >= (1ll << (BitSize - a))) throw "overflow";for (auto& i : d) i <<= a;return normal();}BigDecimal operator>>=(int a) {if (a < 0) return *this <<= -a;while (a >= BitSize) {for (int i = 0; i < IntegerSize + DecimalSize - 1; ++i) d[i] = d[i + 1];d[IntegerSize + DecimalSize - 1] >>= BitSize;a -= BitSize;}for (int i = 0; i < IntegerSize + DecimalSize - 1; ++i) {d[i] |= d[i + 1] << BitSize;d[i + 1] = 0;}for (auto& i : d) i >>= a;return normal();}BigDecimal operator+=(const BigDecimal &a) {if (sign == a.sign) for (int i = 0; i < IntegerSize + DecimalSize; ++i) d[i] += a.d[i];else for (int i = 0; i < IntegerSize + DecimalSize; ++i) d[i] -= a.d[i];return normal();}BigDecimal operator-=(const BigDecimal &a) {return *this += -a;}BigDecimal operator*=(const BigDecimal& a) {BigDecimal res = 0;for (int i = 0; i < IntegerSize + DecimalSize; ++i) {if (i < DecimalSize) res = (res + *this * a.d[i]) >> BitSize;else res += *this * a.d[i] << (i - DecimalSize) * BitSize;}res.sign = (sign == a.sign ? PLUS : MINUS);return *this = res.normal();}BigDecimal operator*=(const unsigned int& a) {for (auto& i : d) i *= a;return this->normal();}BigDecimal operator/=(const BigDecimal &a) {if (a == 0) throw "divide by zero";BigDecimal rev = (double)1 / a.toDouble();for (int i = 0; i < 7; ++i) rev = (rev << 1) - a * rev * rev;rev.sign = a.sign;return *this *= rev;}BigDecimal operator%=(const BigDecimal &a) {if (a == 0) throw "modulo by zero";return *this -= floor(*this / a) * a;}BigDecimal operator-(const BigDecimal& v) const {return BigDecimal(*this) -= v;}BigDecimal operator++() {return *this += 1;}BigDecimal operator++(int) {BigDecimal bd = *this;*this += 1;return bd;}BigDecimal operator--() {return *this -= 1;}BigDecimal operator--(int) {BigDecimal bd = *this;*this -= 1;return bd;}bool operator<(const BigDecimal &a) const {BigDecimal aa = a - EPSILON;if (sign == MINUS) {if (aa.sign == MINUS) return -a < -*this;else return true;}if (aa.sign == MINUS) return false;for (int i = IntegerSize + DecimalSize; i-- > 0; ) if (d[i] != aa.d[i]) return d[i] < aa.d[i];return false;}bool equals(const BigDecimal &a) const {if (sign != a.sign) return false;for (int i = 0; i < IntegerSize + DecimalSize; ++i) if (d[i] != a.d[i]) return false;return true;}int toInt() const {int res = 0;for (int i = 0; i < IntegerSize; ++i) res += d[DecimalSize + i] << BitSize * i;if (sign == MINUS) return -res;return res;}long long toLongLong() const {long long res = 0;for (int i = 0; i < IntegerSize; ++i) res += d[DecimalSize + i] << BitSize * i;if (sign == MINUS) return -res;return res;}string toString(int digit = 100, string mode = "near") const {string str;BigDecimal a = *this, bd = 1;if (a.sign == MINUS) {str += "-";a.sign = PLUS;}if (mode == "near") {BigDecimal round = BigDecimal(0.5);for (int i = 0; i < digit; ++i) round /= 10;a += round + EPSILON;}if (mode == "ceil") {BigDecimal round = 1;for (int i = 0; i < digit; ++i) round /= 10;a += round - EPSILON;}for (; bd <= a; bd *= 10) ++digit;if (bd > 1) {bd /= 10;--digit;}for (int i = 0; i < digit + 1; ++i) {if (bd == 0) {str += "0";continue;}if (bd * 10 == 1) str += ".";int d = 0;while (bd < a) {a -= bd;++d;}if (d > 9) {d -= 10;string::iterator itr = str.end();while (true) {if (itr == str.begin()) {str = "1" + str;break;}--itr;if (*itr == '.') continue;++*itr;if (*itr > '9') *itr = '0';else break;}}str += '0' + d;bd /= 10;}return str;}double toDouble() const {double res = 0;for (int i = 0; i < IntegerSize + DecimalSize; ++i) res += d[i] * pow(2, (i - DecimalSize) * BitSize);if (sign == MINUS) return -res;return res;}bool isPlus() const {return sign == PLUS;}bool isMinus() const {return sign == MINUS;}template<int I, int D>friend BigDecimal<I, D> pow(const BigDecimal<I, D> &x, const BigDecimal<I, D> &y);template<int I, int D>friend BigDecimal<I, D> floor(BigDecimal<I, D> x);};template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> pi() {const static BigDecimal<IntegerSize, DecimalSize> PI = (atan(BigDecimal<IntegerSize, DecimalSize>(1) / 5) << 4) - (atan(BigDecimal<IntegerSize,DecimalSize>(1) / 239) << 2);return PI;}template<int IntegerSize, int DecimalSize>inline BigDecimal<IntegerSize, DecimalSize> operator+(const int& a, BigDecimal<IntegerSize, DecimalSize> b) {return BigDecimal<IntegerSize, DecimalSize>(a) + b;}template<int IntegerSize, int DecimalSize>inline BigDecimal<IntegerSize, DecimalSize> operator-(const int& a, BigDecimal<IntegerSize, DecimalSize> b) {return BigDecimal<IntegerSize, DecimalSize>(a) - b;}template<int IntegerSize, int DecimalSize>inline BigDecimal<IntegerSize, DecimalSize> operator*(const int& a, BigDecimal<IntegerSize, DecimalSize> b) {return BigDecimal<IntegerSize, DecimalSize>(a) * b;}template<int IntegerSize, int DecimalSize>inline BigDecimal<IntegerSize, DecimalSize> operator/(const int& a, BigDecimal<IntegerSize, DecimalSize> b) {return BigDecimal<IntegerSize, DecimalSize>(a) / b;}template<int IntegerSize, int DecimalSize>ostream &operator<<(ostream &os, BigDecimal<IntegerSize, DecimalSize> a) {os << a.toString(os.precision());return os;}template<int IntegerSize, int DecimalSize>istream &operator>>(istream &is, BigDecimal<IntegerSize, DecimalSize> &a) {string str;is >> str;a = BigDecimal<IntegerSize, DecimalSize>(str);return is;}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> sin(BigDecimal<IntegerSize, DecimalSize> x) {BigDecimal<IntegerSize, DecimalSize> res = 0, xx = - x * x;for (int i = 1; ; i += 2) {x /= max(i * (i - 1), 1);if (x.equals(0)) break;res += x;x *= xx;}return res;}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> cos(BigDecimal<IntegerSize, DecimalSize> x) {BigDecimal<IntegerSize, DecimalSize> res = 0, xx = - x * x;x = 1;for (int i = 0; ; i += 2) {x /= max(i * (i - 1), 1);if (x.equals(0)) break;res += x;x *= xx;}return res;}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> tan(const BigDecimal<IntegerSize, DecimalSize> &x) {return sin(x) / cos(x);}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> asin(BigDecimal<IntegerSize, DecimalSize> x) {if (abs(x) > 1) throw "out of domain";if (x > 1 / sqrt(BigDecimal<IntegerSize, DecimalSize>(2))) return (pi<IntegerSize, DecimalSize>() >> 1) - asin(sqrt(1 - x * x));if (x < -1 / sqrt(BigDecimal<IntegerSize, DecimalSize>(2))) return -(pi<IntegerSize, DecimalSize>() >> 1) + asin(sqrt(1 - x * x));BigDecimal<IntegerSize, DecimalSize> res = 0, xx = x * x >> 2;for (int i = 0; ; ++i) {x *= max(i * 2 * (i * 2 - 1), 1);x /= max(i * i, 1);auto add = x / (i * 2 + 1);if (add.equals(0)) break;res += add;x *= xx;}return res;}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> acos(const BigDecimal<IntegerSize, DecimalSize> &x) {return (pi<IntegerSize, DecimalSize>() >> 1) - asin(x);}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> atan(BigDecimal<IntegerSize, DecimalSize> x) {if (x.isMinus()) return -atan(-x);if (abs(x) > sqrt(2) + 1) return (pi<IntegerSize, DecimalSize>() >> 1) - atan(1 / x);if (abs(x) > sqrt(2) - 1) return (pi<IntegerSize, DecimalSize>() >> 2) + atan((x - 1) / (x + 1));BigDecimal<IntegerSize, DecimalSize> res = 0, xx = - x * x;for (int i = 1; ; i += 2) {auto add = x / i;if (add.equals(0)) break;res += add;x *= xx;}return res;}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> atan2(const BigDecimal<IntegerSize, DecimalSize> &y, const BigDecimal<IntegerSize, DecimalSize> &x) {if (x == 0) {if (y > 0) return pi<IntegerSize, DecimalSize>() / 2;if (y < 0) return -pi<IntegerSize, DecimalSize>() / 2;throw "origin can't define argument";}if (x.isPlus()) return atan(y / x);if (y.isPlus()) return atan(y / x) + pi<IntegerSize, DecimalSize>();return atan(y / x) - pi<IntegerSize, DecimalSize>();}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> sinh(BigDecimal<IntegerSize, DecimalSize> x) {BigDecimal<IntegerSize, DecimalSize> res = 0, xx = x * x;for (int i = 1; ; i += 2) {x /= max(i * (i - 1), 1);if (x.equals(0)) break;res += x;x *= xx;}return res;}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> cosh(BigDecimal<IntegerSize, DecimalSize> x) {BigDecimal<IntegerSize, DecimalSize> res = 0, xx = x * x;x = 1;for (int i = 0; ; i += 2) {x /= max(i * (i - 1), 1);if (x.equals(0)) break;res += x;x *= xx;}return res;}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> tanh(const BigDecimal<IntegerSize, DecimalSize> &x) {return sinh(x) / cosh(x);}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> exp(const BigDecimal<IntegerSize, DecimalSize> &x) {BigDecimal<IntegerSize, DecimalSize> res = 0, xx = 1;for (int i = 0; ; ++i) {xx /= max(i, 1);if (xx.equals(0)) break;res += xx;xx *= x;}return res;}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> log(const BigDecimal<IntegerSize, DecimalSize> &x) {BigDecimal<IntegerSize, DecimalSize> y = log(x.toDouble());BigDecimal<IntegerSize, DecimalSize> z = x / exp(y);BigDecimal<IntegerSize, DecimalSize> a = (z - 1) / (z + 1);BigDecimal<IntegerSize, DecimalSize> res = 0, b = a, aa = a * a;for (int i = 1; ; i += 2) {if (b.equals(0)) break;res += b / i;b *= aa;}return y + res * 2;}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> log10(const BigDecimal<IntegerSize, DecimalSize> &x) {return log(x) / log(BigDecimal<IntegerSize, DecimalSize>(10));}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> pow(const BigDecimal<IntegerSize, DecimalSize> &x, const BigDecimal<IntegerSize, DecimalSize> &y) {if (x.isMinus()) {if (floor(y) == y) return floor(y).d[DecimalSize] % 2 ? -pow(-x, floor(y)) : pow(-x, floor(y));throw "power of negative number";}return exp(y * log(x));}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> sqrt(const BigDecimal<IntegerSize, DecimalSize> &x) {BigDecimal<IntegerSize, DecimalSize> r = 1 / sqrt(x.toDouble());for (int i = 0; i < 7; ++i) r *= (3 - x * r * r) >> 1;return BigDecimal<IntegerSize, DecimalSize>(1) / r;}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> abs(const BigDecimal<IntegerSize, DecimalSize> &x) {return x.isPlus() ? x : -x;}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> ceil(const BigDecimal<IntegerSize, DecimalSize> &x) {if (x.isMinus()) return -floor(-x);auto f = floor(x);return f == x ? f : x + 1;}template<int IntegerSize, int DecimalSize>BigDecimal<IntegerSize, DecimalSize> floor(BigDecimal<IntegerSize, DecimalSize> x) {if (x.isMinus()) return -ceil(-x);x += BigDecimal<IntegerSize, DecimalSize>::EPSILON;for (int i = 0; i < DecimalSize; ++i) x.d[i] = 0;return x;}typedef long double ld;BigDecimal<> solve(){ll N; cin >> N;vector<BigDecimal<>> A(N+1);A[0] = 4; A[1] = 3;for(int i = 2; i <= N;i++){A[i] = (19*A[i-1] - 12*A[i-2])/4.;}return A[N];}int main(void) {cin.tie(0); ios_base::sync_with_stdio(false);cout << fixed << setprecision(12) << solve() << endl;return 0;}