#655674 (C++17) No.1501 酔歩

提出ソース

結果

問題	No.1501 酔歩
ユーザー	👑 emthrm
提出日時	2021-05-08 20:08:41
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	238 ms / 2,000 ms
コード長	14,950 bytes
コンパイル時間	2,107 ms
コンパイル使用メモリ	208,828 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-17 04:19:06
合計ジャッジ時間	9,532 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	1 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	168 ms 6,940 KB
testcase_06	AC	127 ms 6,940 KB
testcase_07	AC	163 ms 6,944 KB
testcase_08	AC	34 ms 6,940 KB
testcase_09	AC	146 ms 6,940 KB
testcase_10	AC	51 ms 6,944 KB
testcase_11	AC	133 ms 6,944 KB
testcase_12	AC	75 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	1 ms 6,944 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	1 ms 6,944 KB
testcase_18	AC	1 ms 6,940 KB
testcase_19	AC	1 ms 6,940 KB
testcase_20	AC	1 ms 6,944 KB
testcase_21	AC	2 ms 6,940 KB
testcase_22	AC	200 ms 6,940 KB
testcase_23	AC	209 ms 6,940 KB
testcase_24	AC	207 ms 6,940 KB
testcase_25	AC	195 ms 6,940 KB
testcase_26	AC	178 ms 6,944 KB
testcase_27	AC	196 ms 6,944 KB
testcase_28	AC	220 ms 6,944 KB
testcase_29	AC	184 ms 6,940 KB
testcase_30	AC	238 ms 6,940 KB
testcase_31	AC	189 ms 6,940 KB
testcase_32	AC	195 ms 6,940 KB
testcase_33	AC	219 ms 6,940 KB
testcase_34	AC	206 ms 6,940 KB
testcase_35	AC	196 ms 6,944 KB
testcase_36	AC	224 ms 6,940 KB
testcase_37	AC	182 ms 6,940 KB
testcase_38	AC	196 ms 6,940 KB
testcase_39	AC	237 ms 6,940 KB
testcase_40	AC	191 ms 6,940 KB
testcase_41	AC	222 ms 6,940 KB
testcase_42	AC	86 ms 6,944 KB
testcase_43	AC	2 ms 6,940 KB
testcase_44	AC	2 ms 6,944 KB
testcase_45	AC	99 ms 6,940 KB
testcase_46	AC	112 ms 6,940 KB
testcase_47	AC	80 ms 6,944 KB
testcase_48	AC	113 ms 6,944 KB
testcase_49	AC	134 ms 6,940 KB
testcase_50	AC	111 ms 6,944 KB
testcase_51	AC	108 ms 6,940 KB
testcase_52	AC	108 ms 6,940 KB
testcase_53	AC	2 ms 6,940 KB
testcase_54	AC	2 ms 6,940 KB
testcase_55	AC	2 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 1000000007;
// constexpr int MOD = 998244353;
constexpr int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << fixed << setprecision(20);
  }
} iosetup;

template <int Log10Base = 9, int Base = 1000000000>  // Base = 10^{Log10Base}
struct BigInt {
  int sign; std::vector<int> dat;
  BigInt(long long val = 0) { *this = val; }
  BigInt(const std::string &s) { *this = s; }
  std::vector<long long> convert_base(int new_lg10_base, int new_base) const {
    assert(new_base == static_cast<int>(std::round(std::pow(10, new_lg10_base))));
    int mx_base = std::max(Log10Base, new_lg10_base);
    std::vector<long long> p(mx_base + 1, 1);
    for (int i = 1; i <= mx_base; ++i) p[i] = p[i - 1] * 10;
    std::vector<long long> res;
    long long now_val = 0;
    int now_lg10_base = 0;
    for (int e : dat) {
      now_val += p[now_lg10_base] * e;
      now_lg10_base += Log10Base;
      while (now_lg10_base >= new_lg10_base) {
        res.emplace_back(now_val % new_base);
        now_val /= new_base;
        now_lg10_base -= new_lg10_base;
      }
    }
    res.emplace_back(now_val);
    while (!res.empty() && res.back() == 0) res.pop_back();
    return res;
  }
  int digit_sum() const {
    assert(sign == 1);
    std::string s = to_string();
    int res = 0;
    for (char c : s) res += c - '0';
    return res;
  }
  int length() const {
    if (dat.empty()) return 0;
    int res = Log10Base * (dat.size() - 1), tmp = dat.back();
    while (tmp > 0) { ++res; tmp /= 10; }
    return res;
  }
  BigInt pow(BigInt exponent) const {
    BigInt res = 1, tmp = *this;
    while (exponent > 0) {
      if (exponent.dat[0] & 1) res *= tmp;
      tmp *= tmp;
      exponent /= 2;
    }
    return res;
  }
  long long to_llong() const {
    assert(*this >= std::numeric_limits<long long>::min() && *this <= std::numeric_limits<long long>::max());
    long long res = 0;
    for (int i = static_cast<int>(dat.size()) - 1; i >= 0; --i) (res *= Base) += dat[i];
    return res;
  }
  std::string to_string() const { std::stringstream ss; ss << *this; std::string res; ss >> res; return res; }
  void trim() {
    while (!dat.empty() && dat.back() == 0) dat.pop_back();
    if (dat.empty()) sign = 1;
  }
  BigInt &operator=(long long val) {
    sign = 1;
    if (val < 0) { sign = -1; val = -val;}
    dat.clear();
    for (; val > 0; val /= Base) dat.emplace_back(val % Base);
    return *this;
  }
  BigInt &operator=(const std::string &s) {
    sign = 1;
    dat.clear();
    if (!s.empty()) {
      int tail = 0;
      if (s[tail] == '-') {
        sign = -1;
        ++tail;
      } else if (s[tail] == '+') {
        ++tail;
      }
      for (int i = s.length() - 1; i >= tail; i -= Log10Base) {
        int val = 0;
        for (int j = std::max(tail, i - Log10Base + 1); j <= i; ++j) val = val * 10 + (s[j] - '0');
        dat.emplace_back(val);
      }
    }
    trim();
    return *this;
  }
  BigInt &operator=(const BigInt &x) {
    sign = x.sign;
    dat.resize(x.dat.size());
    std::copy(x.dat.begin(), x.dat.end(), dat.begin());
    return *this;
  }
  BigInt &operator+=(const BigInt &x) {
    if (sign == x.sign) {
      bool carry = false;
      for (int i = 0; i < std::max(dat.size(), x.dat.size()) || carry; ++i) {
        if (i == dat.size()) dat.emplace_back(0);
        dat[i] += (i < x.dat.size() ? x.dat[i] : 0) + carry;
        carry = dat[i] >= Base;
        if (carry) dat[i] -= Base;
      }
    } else {
      *this -= -x;
    }
    return *this;
  }
  BigInt &operator-=(const BigInt &x) {
    if (sign == x.sign) {
      BigInt abs_this = *this, abs_x = x;
      abs_this.sign = 1; abs_x.sign = 1;
      if (abs_this >= abs_x) {
        bool carry = false;
        for (int i = 0; i < dat.size() || carry; ++i) {
          dat[i] -= (i < x.dat.size() ? x.dat[i] : 0) + carry;
          carry = dat[i] < 0;
          if (carry) dat[i] += Base;
        }
        trim();
      } else {
        *this = -(x - *this);
      }
    } else {
      *this += -x;
    }
    return *this;
  }
  BigInt &operator*=(const BigInt &x) {
    constexpr int new_log10_base = 6, new_base = 1000000;
    std::vector<long long> this6 = convert_base(new_log10_base, new_base), x6 = x.convert_base(new_log10_base, new_base);
    std::vector<long long> res = karatsuba(this6, 0, this6.size(), x6, 0, x6.size());
    for (int i = 0; i < res.size(); ++i) {
      long long quo = res[i] / new_base;
      if (quo > 0) {
        if (i + 1 == res.size()) res.emplace_back(0);
        res[i + 1] += quo;
      }
      res[i] %= new_base;
    }
    std::string s = (sign * x.sign == 1 ? "+" : "-");
    for (int i = static_cast<int>(res.size()) - 1; i >= 0; --i) {
      std::string tmp = std::to_string(res[i]);
      for (int i = 0; i < new_log10_base - tmp.size(); ++i) s += '0';
      s += tmp;
    }
    return *this = s;
  }
  BigInt &operator/=(int x) { return *this = divide(x).first; }
  BigInt &operator/=(const BigInt &x) { return *this = divide(x).first; }
  BigInt &operator%=(int x) { return *this = divide(x).second; }
  BigInt &operator%=(const BigInt &x) { return *this = divide(x).second; }
  bool operator==(const BigInt &x) const {
    if (sign != x.sign || dat.size() != x.dat.size()) return false;
    int sz = dat.size();
    for (int i = 0; i < sz; ++i) if (dat[i] != x.dat[i]) return false;
    return true;
  }
  bool operator!=(const BigInt &x) const { return !(*this == x); }
  bool operator<(const BigInt &x) const {
    if (sign != x.sign) return sign < x.sign;
    if (dat.size() != x.dat.size()) return sign * dat.size() < x.sign * x.dat.size();
    for (int i = static_cast<int>(dat.size()) - 1; i >= 0; --i) {
      if (dat[i] != x.dat[i]) return dat[i] * sign < x.dat[i] * x.sign;
    }
    return false;
  }
  bool operator<=(const BigInt &x) const { return !(x < *this); }
  bool operator>(const BigInt &x) const { return x < *this; }
  bool operator>=(const BigInt &x) const { return !(*this < x); }
  BigInt &operator++() { return *this += 1; }
  BigInt operator++(int) { BigInt res = *this; ++*this; return res; }
  BigInt &operator--() { return *this -= 1; }
  BigInt operator--(int) { BigInt res = *this; --*this; return res; }
  BigInt operator+() const { return *this; }
  BigInt operator-() const { BigInt res = *this; res.sign = -res.sign; return res; }
  BigInt operator+(const BigInt &x) const { return BigInt(*this) += x; }
  BigInt operator-(const BigInt &x) const { return BigInt(*this) -= x; }
  BigInt operator*(const BigInt &x) const { return BigInt(*this) *= x; }
  BigInt operator/(int x) const { return BigInt(*this) /= x; }
  BigInt operator/(const BigInt &x) const { return BigInt(*this) /= x; }
  BigInt operator%(int x) const { return BigInt(*this) %= x; }
  BigInt operator%(const BigInt &x) const { return BigInt(*this) %= x; }
  friend std::ostream &operator<<(std::ostream &os, const BigInt &x) {
    if (x.sign == -1) os << '-';
    os << (x.dat.empty() ? 0 : x.dat.back());
    for (int i = static_cast<int>(x.dat.size()) - 2; i >= 0; --i) os << std::setw(Log10Base) << std::setfill('0') << x.dat[i];
    return os;
  }
  friend std::istream &operator>>(std::istream &is, BigInt &x) { std::string s; is >> s; x = s; return is; }
private:
  std::vector<long long> karatsuba(std::vector<long long> &a, int a_l, int a_r, std::vector<long long> &b, int b_l, int b_r) const {
    int a_len = a_r - a_l, b_len = b_r - b_l;
    if (a_len < b_len) return karatsuba(b, b_l, b_r, a, a_l, a_r);
    std::vector<long long> res(a_len + b_len, 0);
    if (b_len <= 32) {
      for (int i = a_l; i < a_r; ++i) for (int j = b_l; j < b_r; ++j) res[(i - a_l) + (j - b_l)] += a[i] * b[j];
    } else {
      int mid = (a_len + 1) / 2, n = std::min(a_len, mid);
      for (int i = a_l; i + mid < a_r; ++i) a[i] += a[i + mid];
      for (int i = b_l; i + mid < b_r; ++i) b[i] += b[i + mid];
      std::vector<long long> tmp = karatsuba(a, a_l, a_l + mid, b, b_l, b_l + n);
      for (int i = 0; i < tmp.size(); ++i) res[mid + i] = tmp[i];
      for (int i = a_l; i + mid < a_r; ++i) a[i] -= a[i + mid];
      for (int i = b_l; i + mid < b_r; ++i) b[i] -= b[i + mid];
      tmp = karatsuba(a, a_l, a_l + mid, b, b_l, b_l + n);
      for (int i = 0; i < tmp.size(); ++i) { res[i] += tmp[i]; res[mid + i] -= tmp[i]; }
      tmp = karatsuba(a, a_l + mid, a_r, b, b_l + n, b_r);
      for (int i = 0; i < tmp.size(); ++i) { res[mid + i] -= tmp[i]; res[(mid << 1) + i] += tmp[i]; }
    }
    while (!res.empty() && res.back() == 0) res.pop_back();
    return res;
  }
  std::pair<BigInt, int> divide(int x) const {
    assert(x != 0);
    BigInt dividend = *this;
    if (x < 0) { dividend.sign = -dividend.sign; x = -x; }
    long long rem = 0;
    for (int i = static_cast<int>(dividend.dat.size()) - 1; i >= 0; --i) {
      long long tmp = rem * Base + dividend.dat[i];
      dividend.dat[i] = static_cast<int>(tmp / x);
      rem = tmp % x;
    }
    dividend.trim();
    return {dividend, static_cast<int>(rem)};
  }
  std::pair<BigInt, BigInt> divide(const BigInt &x) const {
    assert(!x.dat.empty());
    int k = Base / (x.dat.back() + 1);
    BigInt dividend = *this, divisor = x;
    dividend.sign = 1; divisor.sign = 1;
    dividend *= k; divisor *= k;
    BigInt quo, rem = 0;
    quo.dat.resize(dividend.dat.size());
    int sz = divisor.dat.size();
    for (int i = static_cast<int>(dividend.dat.size()) - 1; i >= 0; --i) {
      rem.dat.insert(rem.dat.begin(), dividend.dat[i]);
      quo.dat[i] = static_cast<int>(((sz < rem.dat.size() ? static_cast<long long>(rem.dat[sz]) * Base : 0) + (sz - 1 < rem.dat.size() ? rem.dat[sz - 1] : 0)) / divisor.dat.back());
      rem -= divisor * quo.dat[i];
      while (rem.sign == -1) { rem += divisor; --quo.dat[i];  }
    }
    quo.sign = sign * x.sign; rem.sign = sign;
    quo.trim(); rem.trim();
    return {quo, rem / k};
  }
};
namespace std {
template <int Log10Base, int Base>
BigInt<Log10Base, Base> __gcd(BigInt<Log10Base, Base> a, BigInt<Log10Base, Base> b) { while (!b.dat.empty()) std::swap(a %= b, b); return a; }
template <int Log10Base, int Base>
BigInt<Log10Base, Base> __lcm(const BigInt<Log10Base, Base> &a, const BigInt<Log10Base, Base> &b) { return a / std::__gcd(a, b) * b; }
template <int Log10Base, int Base>
BigInt<Log10Base, Base> abs(const BigInt<Log10Base, Base> &x) { BigInt<Log10Base, Base> res = x; res.sign = 1; return res; }
template <int Log10Base, int Base>
BigInt<Log10Base, Base> max(const BigInt<Log10Base, Base> &a, const BigInt<Log10Base, Base> &b) { return a < b ? b : a; }
template <int Log10Base, int Base>
BigInt<Log10Base, Base> min(const BigInt<Log10Base, Base> &a, const BigInt<Log10Base, Base> &b) { return a < b ? a : b; }
}  // std

template <typename T = long long>
struct Rational {
  T num, den;
  Rational(): num(0), den(1) {}
  Rational(T num, T den = 1) : num(num), den(den) { assert(den != 0); reduce(); }
  template <typename Real = long double> Real to_real() const { return static_cast<Real>(num) / den; }
  Rational &operator+=(const Rational &x) {
    T g = std::__gcd(den, x.den);
    num = num * (x.den / g) + x.num * (den / g); den *= x.den / g;
    reduce();
    return *this;
  }
  Rational &operator-=(const Rational &x) { return *this += -x; }
  Rational &operator*=(const Rational &x) {
    T g1 = std::__gcd(num, x.den), g2 = std::__gcd(den, x.num);
    num = (num / g1) * (x.num / g2); den = (den / g2) * (x.den / g1);
    reduce();
    return *this;
  }
  Rational &operator/=(const Rational &x) { return *this *= Rational(x.den, x.num); }
  bool operator==(const Rational &x) const { return num == x.num && den == x.den; }
  bool operator!=(const Rational &x) const { return !(*this == x); }
  bool operator<(const Rational &x) const { return (x - *this).num > 0; }
  bool operator<=(const Rational &x) const { return !(x < *this); }
  bool operator>(const Rational &x) const { return x < *this; }
  bool operator>=(const Rational &x) const { return !(*this < x); }
  Rational &operator++() { if ((num += den) == 0) den = 1; return *this; }
  Rational operator++(int) { Rational res = *this; ++*this; return res; }
  Rational &operator--() { if ((num -= den) == 0) den = 1; return *this; }
  Rational operator--(int) { Rational res = *this; --*this; return res; }
  Rational operator+() const { return *this; }
  Rational operator-() const { return Rational(-num, den); }
  Rational operator+(const Rational &x) const { return Rational(*this) += x; }
  Rational operator-(const Rational &x) const { return Rational(*this) -= x; }
  Rational operator*(const Rational &x) const { return Rational(*this) *= x; }
  Rational operator/(const Rational &x) const { return Rational(*this) /= x; }
  // friend std::ostream &operator<<(std::ostream &os, const Rational &x) {
  //   if (x.den == 1) return os << x.num;
  //   return os << x.num << '/' << x.den;
  // }
private:
  void reduce() { T g = std::__gcd(num, den); num /= g; den /= g; if (den < 0) { num = -num; den = -den; } }
};
namespace std {
template <typename T> Rational<T> abs(const Rational<T> &x) {Rational<T> res = x; if (res.num < 0) res.num = -res.num; return res; }
template <typename T> Rational<T> max(const Rational<T> &a, const Rational<T> &b) { return a < b ? b : a; }
template <typename T> Rational<T> min(const Rational<T> &a, const Rational<T> &b) { return a < b ? a : b; }
template <typename T> struct numeric_limits<Rational<T>> {
  static constexpr Rational<T> max() { return std::numeric_limits<T>::max(); }
  static constexpr Rational<T> lowest() { return std::numeric_limits<T>::lowest(); }
};
}  // std

int main() {
  int n, k; cin >> n >> k; --k;
  if (n == 1) {
    cout << "1/1\n";
    return 0;
  }
  if (k == 0) {
    cout << "0\n";
    return 0;
  }
  if (n == 2) {
    cout << "1/1\n";
    return 0;
  }
  vector<int> a(n); REP(i, n) cin >> a[i];
  using rational = Rational<__int128_t>;
  vector p(n, rational(0));
  p[1] = rational(a[2], a[0] + a[2]);
  FOR(i, 2, n - 1) {
    int ball = a[i - 1] + a[i + 1];
    p[i] = rational(a[i + 1], ball) / (-p[i - 1] * rational(a[i - 1], ball) + rational(1));
  }
  rational ans(1);
  FOR(i, k, n - 1) ans *= p[i];
  cout << static_cast<ll>(ans.num) << '/' << static_cast<ll>(ans.den) << '\n';
  return 0;
}

yukicoder

結果

テストケース

ソースコード