#121462 (C++11（廃止可能性あり）) No.428 小数から逃げる夢

提出ソース
結果

問題	No.428 小数から逃げる夢
コンテスト
ユーザー	yuppe19 😺
提出日時	2016-10-04 09:54:24
言語	C++11（廃止可能性あり） (gcc 13.3.0)
結果	AC
実行時間	2 ms / 1,000 ms
コード長	11,017 bytes
コンパイル時間	1,273 ms
コンパイル使用メモリ	96,744 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-11-21 15:33:00
合計ジャッジ時間	3,679 ms
ジャッジサーバーID （参考情報）	judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 100
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <tuple>
#include <vector>
#include <sstream>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;

constexpr int BASE_DIGITS = 4;
constexpr int BASE = 10000;
struct bigint {
  // 10**4進法。4桁ごとに区切るイメージ。
  bigint(void);
  bigint(const int size);
  bigint(const string val);
  bigint(const i64 val);
  static bigint valueOf(const i64);
  bigint& abs(bigint&);
  bigint& operator = (const bigint&);
  bigint operator + (const bigint&) const;
  bigint operator - () const;
  bigint operator - (const bigint&) const;
  bigint operator * (const bigint&) const;
  bigint& operator += (const bigint&);
  bigint& operator -= (const bigint&);
  bigint& operator *= (const bigint&);
  bigint& operator *= (const i64&);
  bool operator <  (bigint&);
  bigint pow(const int) const;
  friend ostream& operator << (ostream&, const bigint&);
  string to_string(void);
private:
  int minus;
  int n; // vの要素数
  vector<i64> v;
  inline bool absGreater(const bigint&, const bigint&) const;
  inline bigint add(const bigint&, const bigint&) const;
  inline bigint sub(const bigint&, const bigint&) const;
  inline bigint fftmul(const bigint&, const bigint&) const;
  inline vector<i64> karatsuba(const vector<i64>&, const vector<i64>&) const;
  inline bigint karatsuba(const bigint&, const bigint&) const;
  static bigint pow(const bigint&, const bigint&, const int);
};

struct FMT {
  static void fmt(const int, vector<i64>*);
  static void ifmt(const int, vector<i64>*);
  static void convol(const int, vector<i64>*, vector<i64>*);
private:
  static constexpr i64 N = 5LL << 37;
  static constexpr i64 O = 2003LL;
  static constexpr i64 M = N * 211 + 1;
  static void myfmt(const int, vector<i64>*, const bool);
};

inline i64 mod_mul(const i64& x, const i64& y, const i64& m) {
  // yとmの最大ビット長はともに48ビット。
  // http://codeforces.com/blog/entry/15884
  // 12 < floor(63 - log2(MAX_VALUE)) = 15
  // 0xfff = (1<<12) - 1
  i64 b, res = y * (x & 0xfff);
  res += (b=(y<<12) % m) * ((x>>12) & 0xfff);
  res += (b=(b<<12) % m) * ((x>>24) & 0xfff);
  res += (b<<12) % m     * ((x>>36) & 0xfff);
  res %= m;
  return res;
}

inline tuple<i64, i64, i64> extgcd(const i64& x, const i64& y) {
  if(y == 0) { return make_tuple(1LL, 0LL, x); }
  i64 a, b, d; tie(a, b, d) = extgcd(y, x%y);
  return make_tuple(b, a-x/y*b, d);
}

inline i64 mod_inv(const i64 a, const i64 m) {
  i64 x, _, d; tie(x, _, d) = extgcd(a, m);
  return (x % m + m) % m;
}

inline i64 mod_pow(const i64& a, const i64& r, const i64& n, const i64& m) {
  if(n == 0) { return r; }
  if(n & 1)  { return mod_pow(a, mod_mul(a, r, m), n-1, m); }
  return mod_pow(mod_mul(a, a, m), r, n>>1, m);
}

inline i64 mod_pow(const i64 a, const i64 n, const i64 m) {
  return mod_pow(a, 1, n, m);
}

void FMT::myfmt(const int logn, vector<i64> *a, const bool inv) {
  const int n = 1 << logn;
  for(int H=1, W=n>>1; H<n; H<<=1, W>>=1) {
    vector<i64> y = *a;
    i64 r = mod_pow(O, N/(H*2), M);
    if(inv) { r = mod_inv(r, M); }
    i64 w = 1;
    for(int k=0; k<H; ++k) {
      for(int j=0; j<W; ++j) {
        i64 y0 = y[2*W*k+j],
            y1 = mod_mul(y[2*W*k+j+W], w, M);
        a->at(W* k   +j) = y0 + y1 < M ? y0 + y1     : y0 + y1 - M;
        a->at(W*(k+H)+j) = y0 < y1     ? y0 - y1 + M : y0 - y1;
      }
      w = mod_mul(w, r, M);
    }
  }
}

void FMT::fmt(const int logn, vector<i64> *a) {
  myfmt(logn, a, false);
}

void FMT::ifmt(const int logn, vector<i64> *a) {
  myfmt(logn, a, true);
  int n = 1 << logn;
  i64 inv = mod_inv(n, M);
  for(int i=0; i<n; ++i) {
    a->at(i) = mod_mul(a->at(i), inv, M);
  }
}

void FMT::convol(const int logn, vector<i64> *a, vector<i64> *b) {
  fmt(logn, a);
  fmt(logn, b);
  for(int i=0; i<1<<logn; ++i) {
    a->at(i) = mod_mul(a->at(i), b->at(i), M);
  }
  ifmt(logn, a);
}

bigint::bigint(void) {}

bigint::bigint(const int size) {
  n = size;
  v.assign(size, 0LL);
}

bigint::bigint(const string s) {
  minus = s[0] == '-';
  int last = s.size();
  int m = last - minus; // 桁数
  n = (m + BASE_DIGITS - 1) / BASE_DIGITS;
  v.assign(n, 0LL);
  for(int i=last-1, k=0; i>=minus; i-=BASE_DIGITS, ++k) {
    for(int j=max(minus, i-BASE_DIGITS+1); j<=i; ++j) {
      v[k] = v[k] * 10 + s[j] - '0';
    }
  }
  if(v[n-1] == 0) { minus = false; } // -0にはしない
}

bigint::bigint(const i64 x) {
  *this = bigint::valueOf(x);
}

bigint bigint::valueOf(const i64 x) {
  constexpr int N = 5;
  bigint res(N);
  res.minus = x < 0;
  i64 y = x;
  for(int i=0; i<N; ++i) {
    int z = y % BASE;
    res.v[i] = ::abs(y % BASE);
    y /= BASE;
  }
  while(res.v[res.n-1] == 0 && res.n > 1) { --res.n; }
  res.v.resize(res.n);
  if(res.v[res.n-1] == 0) { res.minus = false; } // -0にはしない
  return res;
}

bigint& bigint::operator = (const bigint &other) {
  minus = other.minus;
  n = other.n;
  v = other.v;
  return *this;
}

bool bigint::absGreater(const bigint& a, const bigint& b) const {
  // abs(a) < abs(b)かどうか。minusフラグを見ずにチェックすればいい。
  if(a.n != b.n) { return a.n < b.n; }
  for(int i=a.n-1; i>=0; --i) {
    if(a.v[i] != b.v[i]) { return a.v[i] < b.v[i]; }
  }
  return false; // abs(a) == abs(b)のときはfalseを返す
}

bool bigint::operator < (bigint& other) {
  if(minus != other.minus) { return minus; }
  return absGreater(*this, other) ^ minus;
}

bigint bigint::add(const bigint& a, const bigint& b) const {
  // abs(a) + abs(b) を計算する
  int size = max(a.n, b.n) + 1;
  bigint res(size);
  for(int i=0; i<a.n; ++i) { res.v[i] += a.v[i]; }
  for(int i=0; i<b.n; ++i) { res.v[i] += b.v[i]; }
  for(int i=0; i<size; ++i) {
    if(res.v[i] >= BASE) { // 繰り上がり
      ++res.v[i+1];
      res.v[i] -= BASE;
    }
  }
  while(res.v[res.n-1] == 0 && res.n > 1) { --res.n; }
  res.v.resize(res.n);
  return res;
}

bigint& bigint::abs(bigint& a) {
  a.minus = false;
  return a;
}

bigint bigint::sub(const bigint& a, const bigint& b) const {
  // 必ず abs(a) >= abs(b) になるように引数は来る
  // abs(a) - abs(b) を計算する
  int size = max(a.n, b.n) + 1;
  bigint res(size);
  for(int i=0; i<a.n; ++i) { res.v[i] += a.v[i]; }
  for(int i=0; i<b.n; ++i) { res.v[i] -= b.v[i]; }
  for(int i=0; i<size; ++i) {
    if(res.v[i] < 0) { // 借りてくる
      --res.v[i+1];
      res.v[i] += BASE;
    }
  }
  while(res.v[res.n-1] == 0 && res.n > 1) { --res.n; }
  res.v.resize(res.n);
  return res;
}

bigint bigint::operator + (const bigint& other) const {
  bigint res;
  if(minus == other.minus) { // +, + or -, -
    res = add(*this, other);
    res.minus = minus;
  } else if(absGreater(*this, other)) { // +, - or -, +
    res = sub(other, *this);
    res.minus = other.minus;
  } else {
    res = sub(*this, other);
    res.minus = minus;
  }
  if(res.n == 1 && res.v[0] == 0) { res.minus = false; }
  return res;
}

bigint bigint::operator - () const {
  bigint obj = *this;
  obj.minus = !minus;
  return obj;
}

bigint bigint::operator - (const bigint& other) const {
  return *this + (-other);
}

bigint bigint::fftmul(const bigint& a, const bigint& b) const {
  int size = max(a.n, b.n) * 2;
  int m; for(m=0; 1<<m < size; ++m) /* nop */ ;
  bigint res(1<<m);
  vector<i64> c(1<<m, 0);
  for(int i=0; i<a.n; ++i) { res.v[i] = a.v[i]; }
  for(int i=0; i<b.n; ++i) { c[i]     = b.v[i]; }
  FMT::convol(m, &res.v, &c);
  for(int i=0; i<(1<<m)-1; ++i) {
    res.v[i+1] += res.v[i] / BASE;
    res.v[i]   %= BASE;
  }
  while(res.v[res.n-1] == 0 && res.n > 1) { --res.n; }
  res.v.resize(res.n);
  res.minus = a.minus ^ b.minus;
  return res;
}

vector<i64> bigint::karatsuba(const vector<i64>& a, const vector<i64>& b) const {
  int n = a.size();
  vector<i64> res(n + n);
  if(n <= 32) {
    for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) res[i+j] += a[i] * b[j];
    return res;
  }
  int k = n >> 1;
  vector<i64> a1(begin(a), begin(a) + k),
              a2(begin(a) + k, end(a)),
              b1(begin(b), begin(b) + k),
              b2(begin(b) + k, end(b)),
              a1b1 = karatsuba(a1, b1),
              a2b2 = karatsuba(a2, b2);
  for(int i=0; i<k; ++i) { a2[i] += a1[i]; b2[i] += b1[i]; }
  vector<i64> r = karatsuba(a2, b2);
  for(int i=0, m=a1b1.size(); i<m; ++i) { r[i]     -= a1b1[i]; }
  for(int i=0, m=a2b2.size(); i<m; ++i) { r[i]     -= a2b2[i]; }
  for(int i=0, m=r.size();    i<m; ++i) { res[i+k] += r[i]; }
  for(int i=0, m=a1b1.size(); i<m; ++i) { res[i]   += a1b1[i]; }
  for(int i=0, m=a2b2.size(); i<m; ++i) { res[i+n] += a2b2[i]; }
  return res;
}

bigint bigint::karatsuba(const bigint& ba, const bigint& bb) const {
  vector<i64> a(begin(ba.v), end(ba.v)),
              b(begin(bb.v), end(bb.v));
  int size = max(ba.n, bb.n);
  int m; for(m=0 ; 1<<m < size; ++m) /* nop */ ;
  a.resize(1<<m); b.resize(1<<m);
  vector<i64> c = karatsuba(a, b);
  int cn = c.size();
  bigint res(cn);
  for(int i=0; i<cn-1; ++i) {
    res.v[i]   += c[i];
    res.v[i+1] += res.v[i] / BASE;
    res.v[i]   %= BASE;
  }
  while(res.v[res.n-1] == 0 && res.n > 1) { --res.n; }
  res.v.resize(res.n);
  res.minus = ba.minus ^ bb.minus;
  return res;
}

bigint bigint::operator * (const bigint& other) const {
//  return max(n, other.n) < 1000 ? karatsuba(*this, other) : fftmul(*this, other);
  return fftmul(*this, other);
}

bigint& bigint::operator += (const bigint& other) {
  *this = *this + other;
  return *this;
}

bigint& bigint::operator -= (const bigint& other) {
  *this = *this - other;
  return *this;
}

bigint& bigint::operator *= (const bigint& other) {
  *this = *this * other;
  return *this;
}

bigint& bigint::operator *= (const i64& other) {
  *this = *this * bigint::valueOf(other);
  return *this;
}

bigint bigint::pow(const bigint &x, const bigint &r, const int n) {
  if(n == 0) { return r; }
  if(n & 1)  { return pow(x, r*x, n-1); }
  return pow(x*x, r, n>>1);
}

bigint bigint::pow(const int n) const {
  return bigint::pow(*this, bigint::valueOf(1LL), n);
}

ostream& operator << (ostream &stream, const bigint &a) {
  if(a.minus) { stream << '-'; }
  stream << a.v[a.n-1];
  for(int i=a.n-2; i>=0; --i) {
    stream << setw(BASE_DIGITS) << setfill('0') << a.v[i];
  }
  return stream;
}

string bigint::to_string() {
  stringstream ss;
  if(minus) { ss << '-'; }
  ss << v[n-1];
  for(int i=n-2; i>=0; --i) {
    ss << setw(BASE_DIGITS) << setfill('0') << v[i];
  }
  string t = ss.str();
  return t;
}

int main(void) {
  cin.tie(0); ios::sync_with_stdio(false);
  const string s = "1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991";
  const int N = s.size();
  bigint x(s);
  int n; cin >> n;
  x *= n;

  string t = x.to_string();
  int m = t.size();
  if(m == N) {
    t = "0." + t;
  } else {
    t.insert(m-N, ".");
  }
  cout << t << '\n';

  return 0;
}
yukicoder

結果

ソースコード
