結果
| 問題 |
No.53 悪の漸化式
|
| コンテスト | |
| ユーザー |
 sune232002
|
| 提出日時 | 2014-11-01 15:02:08 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 37 ms / 5,000 ms |
| コード長 | 11,361 bytes |
| コンパイル時間 | 2,548 ms |
| コンパイル使用メモリ | 188,784 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-12-30 15:56:59 |
| 合計ジャッジ時間 | 3,605 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 20 |
ソースコード
#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;
}
}