#334331 (C++14) No.3055 2019（注：異常な難易度です）

提出ソース

結果

問題	No.3055 2019（注：異常な難易度です）
ユーザー	risujiroh
提出日時	2019-04-01 23:51:45
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	10 ms / 2,000 ms
コード長	9,263 bytes
コンパイル時間	2,432 ms
コンパイル使用メモリ	199,832 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-11-27 05:52:33
合計ジャッジ時間	4,652 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	1 ms 6,816 KB
testcase_04	AC	2 ms 6,820 KB
testcase_05	AC	1 ms 6,816 KB
testcase_06	AC	1 ms 6,820 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	1 ms 6,816 KB
testcase_09	AC	1 ms 6,820 KB
testcase_10	AC	2 ms 6,820 KB
testcase_11	AC	1 ms 6,820 KB
testcase_12	AC	2 ms 6,820 KB
testcase_13	AC	2 ms 6,820 KB
testcase_14	AC	1 ms 6,820 KB
testcase_15	AC	2 ms 6,820 KB
testcase_16	AC	1 ms 6,816 KB
testcase_17	AC	2 ms 6,820 KB
testcase_18	AC	2 ms 6,816 KB
testcase_19	AC	1 ms 6,816 KB
testcase_20	AC	2 ms 6,820 KB
testcase_21	AC	2 ms 6,816 KB
testcase_22	AC	2 ms 6,816 KB
testcase_23	AC	1 ms 6,816 KB
testcase_24	AC	1 ms 6,820 KB
testcase_25	AC	2 ms 6,820 KB
testcase_26	AC	1 ms 6,816 KB
testcase_27	AC	2 ms 6,816 KB
testcase_28	AC	2 ms 6,820 KB
testcase_29	AC	2 ms 6,820 KB
testcase_30	AC	2 ms 6,820 KB
testcase_31	AC	2 ms 6,820 KB
testcase_32	AC	2 ms 6,816 KB
testcase_33	AC	1 ms 6,816 KB
testcase_34	AC	1 ms 6,816 KB
testcase_35	AC	2 ms 6,820 KB
testcase_36	AC	2 ms 6,820 KB
testcase_37	AC	2 ms 6,816 KB
testcase_38	AC	2 ms 6,820 KB
testcase_39	AC	2 ms 6,816 KB
testcase_40	AC	2 ms 6,816 KB
testcase_41	AC	1 ms 6,816 KB
testcase_42	AC	1 ms 6,820 KB
testcase_43	AC	2 ms 6,816 KB
testcase_44	AC	2 ms 6,820 KB
testcase_45	AC	2 ms 6,820 KB
testcase_46	AC	2 ms 6,816 KB
testcase_47	AC	2 ms 6,816 KB
testcase_48	AC	2 ms 6,820 KB
testcase_49	AC	1 ms 6,820 KB
testcase_50	AC	1 ms 6,820 KB
testcase_51	AC	2 ms 6,816 KB
testcase_52	AC	2 ms 6,820 KB
testcase_53	AC	1 ms 6,816 KB
testcase_54	AC	2 ms 6,816 KB
testcase_55	AC	2 ms 6,816 KB
testcase_56	AC	2 ms 6,820 KB
testcase_57	AC	2 ms 6,816 KB
testcase_58	AC	2 ms 6,816 KB
testcase_59	AC	2 ms 6,816 KB
testcase_60	AC	2 ms 6,816 KB
testcase_61	AC	1 ms 6,820 KB
testcase_62	AC	2 ms 6,820 KB
testcase_63	AC	2 ms 6,816 KB
testcase_64	AC	2 ms 6,816 KB
testcase_65	AC	2 ms 6,816 KB
testcase_66	AC	2 ms 6,816 KB
testcase_67	AC	2 ms 6,816 KB
testcase_68	AC	2 ms 6,820 KB
testcase_69	AC	2 ms 6,820 KB
testcase_70	AC	2 ms 6,816 KB
testcase_71	AC	2 ms 6,816 KB
testcase_72	AC	2 ms 6,816 KB
testcase_73	AC	2 ms 6,820 KB
testcase_74	AC	3 ms 6,816 KB
testcase_75	AC	3 ms 6,816 KB
testcase_76	AC	3 ms 6,816 KB
testcase_77	AC	3 ms 6,820 KB
testcase_78	AC	3 ms 6,820 KB
testcase_79	AC	3 ms 6,820 KB
testcase_80	AC	3 ms 6,816 KB
testcase_81	AC	4 ms 6,820 KB
testcase_82	AC	5 ms 6,816 KB
testcase_83	AC	6 ms 6,820 KB
testcase_84	AC	7 ms 6,816 KB
testcase_85	AC	8 ms 6,820 KB
testcase_86	AC	8 ms 6,820 KB
testcase_87	AC	9 ms 6,820 KB
testcase_88	AC	9 ms 6,816 KB
testcase_89	AC	10 ms 6,816 KB
testcase_90	AC	9 ms 6,820 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

template<unsigned P> struct ModInt {
  using M = ModInt;
  unsigned v;
  ModInt() : v(0) {}
  template<class Z> ModInt(Z x) : v(x >= 0 ? x % P : (P - -x % P) % P) {}
  constexpr ModInt(unsigned v, int) : v(v) {}
  static constexpr unsigned p() { return P; }
  M operator+() const { return *this; }
  M operator-() const { return {v ? P - v : 0, 0}; }
  explicit operator bool() const noexcept { return v; }
  bool operator!() const noexcept { return !(bool) *this; }
  M operator*(M r) const { return M(*this) *= r; }
  M operator/(M r) const { return M(*this) /= r; }
  M operator+(M r) const { return M(*this) += r; }
  M operator-(M r) const { return M(*this) -= r; }
  bool operator==(M r) const { return v == r.v; }
  bool operator!=(M r) const { return !(*this == r); }
  M& operator*=(M r) { v = (uint64_t) v * r.v % P; return *this; }
  M& operator/=(M r) { return *this *= r.inv(); }
  M& operator+=(M r) { if ((v += r.v) >= P) v -= P; return *this; }
  M& operator-=(M r) { if ((v += P - r.v) >= P) v -= P; return *this; }
  M inv() const {
    int a = v, b = P, x = 1, u = 0;
    while (b) {
      int q = a / b;
      swap(a -= q * b, b);
      swap(x -= q * u, u);
    }
    assert(a == 1);
    return x;
  }
  template<class Z> M pow(Z n) const {
    if (n < 0) return pow(-n).inv();
    M res = 1;
    for (M a = *this; n; a *= a, n >>= 1) if (n & 1) res *= a;
    return res;
  }
  template<class Z> friend M operator*(Z l, M r) { return M(l) *= r; }
  template<class Z> friend M operator/(Z l, M r) { return M(l) /= r; }
  template<class Z> friend M operator+(Z l, M r) { return M(l) += r; }
  template<class Z> friend M operator-(Z l, M r) { return M(l) -= r; }
  friend ostream& operator<<(ostream& os, M r) { return os << r.v; }
  friend istream& operator>>(istream& is, M& r) { lint x; is >> x; r = x; return is; }
  template<class Z> friend bool operator==(Z l, M r) { return M(l) == r; }
  template<class Z> friend bool operator!=(Z l, M r) { return !(l == r); }
};
template<unsigned P, unsigned g> void ntt(V< ModInt<P> >& a, bool inv = false) {
  int n = a.size();
  int j = 0;
  for (int i = 1; i < n; ++i) {
    int k = n >> 1;
    while (j >= k) j -= k, k >>= 1;
    j += k;
    if (i < j) swap(a[i], a[j]);
  }
  assert((P - 1) % n == 0);
  auto xi = ModInt<P>(g).pow((P - 1) / n);
  if (inv) xi = xi.inv();
  for (int k = 1; k < n; k <<= 1) {
    ModInt<P> dt = xi.pow((n >> 1) / k);
    for (int i0 = 0; i0 < n; i0 += k << 1) {
      ModInt<P> t = 1;
      for (int i = i0; i < i0 + k; ++i) {
        j = i + k;
        a[j] *= t, t *= dt;
        tie(a[i], a[j]) = make_pair(a[i] + a[j], a[i] - a[j]);
      }
    }
  }
}
template<unsigned P, unsigned g = 6420> void multiply(V< ModInt<P> >& a, V< ModInt<P> >& b) {
  assert(!a.empty() and !b.empty());
  int n = 1 << __lg(2 * (a.size() + b.size() - 1) - 1);
  a.resize(n), b.resize(n);
  ntt<P, g>(a), ntt<P, g>(b);
  for (int i = 0; i < n; ++i) a[i] *= b[i];
  ntt<P, g>(a, true);
  auto inv_n = ModInt<P>(n).inv();
  for (int i = 0; i < n; ++i) a[i] *= inv_n;
}
void multiply(V<lint>& a, const V<lint>& b) {
  using Mint0 = ModInt<1811939329>;
  using Mint1 = ModInt<2013265921>;
  int n = a.size(), m = b.size();
  V<Mint0> a0(n), b0(m);
  V<Mint1> a1(n), b1(m);
  for (int i = 0; i < n; ++i) a0[i] = a[i], a1[i] = a[i];
  for (int j = 0; j < m; ++j) b0[j] = b[j], b1[j] = b[j];
  multiply(a0, b0);
  multiply(a1, b1);
  n = a0.size();
  a.resize(n);
  auto inv = Mint1(Mint0::p()).inv();
  for (int i = 0; i < n; ++i) {
    a[i] = a0[i].v + (lint) Mint0::p() * ((a1[i] - a0[i].v) * inv).v;
  }
}
struct Bint {
  bool neg;
  string s;
  Bint() : neg(false), s("0") {}
  Bint(const string& x) : neg(x[0] == '-'), s(x.substr(neg)) {}
  Bint(lint x) : neg(x < 0), s(to_string(abs(x))) {}
  Bint(bool neg, const string& s) : neg(neg), s(s) {}
  Bint operator+() const { return *this; }
  Bint operator-() const { return {!neg, s}; }
  explicit operator bool() const noexcept { return s != "0"; }
  bool operator!() const noexcept { return !(bool) *this; }
  Bint operator*(const Bint& r) const { return Bint(*this) *= r; }
  Bint operator/(const Bint& r) const { return Bint(*this) /= r; }
  Bint operator%(const Bint& r) const { return Bint(*this) %= r; }
  Bint operator+(const Bint& r) const { return Bint(*this) += r; }
  Bint operator-(const Bint& r) const { return Bint(*this) -= r; }
  bool operator<(const Bint& r) const {
    if (neg != r.neg) return neg;
    return neg ^ (s.size() != r.s.size() ? s.size() < r.s.size() : s < r.s);
  }
  bool operator>(const Bint& r) const { return r < *this; }
  bool operator<=(const Bint& r) const { return !(*this > r); }
  bool operator>=(const Bint& r) const { return !(*this < r); }
  bool operator==(const Bint& r) const { return neg == r.neg and s == r.s; }
  bool operator!=(const Bint& r) const { return !(*this == r); }
  Bint& operator*=(const Bint& r) {
    if (!*this or !r) {
      neg = false, s = "0";
      return *this;
    }
    neg ^= r.neg;
    auto t = r.s;
    if (s.size() + t.size() < 20) {
      s = to_string(stoull(s) * stoull(t));
      return *this;
    }
    constexpr int D = 6;
    constexpr int B = 1e6;
    V<lint> a;
    for (int i = s.size(); i > 0; i -= D) {
      a.push_back(stoi(s.substr(max(i - D, 0), min(D, i))));
    }
    V<lint> b;
    for (int i = t.size(); i > 0; i -= D) {
      b.push_back(stoi(t.substr(max(i - D, 0), min(D, i))));
    }
    multiply(a, b);
    V<> res;
    lint c = 0;
    for (int i = 0; i < (int) a.size(); ++i) {
      res.push_back((c += a[i]) % B);
      c /= B;
    }
    s = to_string(c);
    while (!res.empty()) {
      auto t = to_string(res.back());
      while (t.size() < D) t = '0' + t;
      s += t;
      res.pop_back();
    }
    int i = 0;
    while (i < (int) s.size() and s[i] == '0') ++i;
    s = s.substr(i);
    return *this;
  }
  Bint& operator/=(const Bint& r) {
    assert(r);
    auto t = r.s;
    if (Bint(s) < Bint(t)) {
      neg = false, s = "0";
      return *this;
    }
    neg ^= r.neg;
    string res;
    for (int i = s.size() - t.size(); i >= 0; --i) {
      char c = '0';
      while (Bint(s) >= Bint(t + string(i, '0'))) {
        s = (Bint(s) - Bint(t + string(i, '0'))).s;
        ++c;
      }
      res += c;
    }
    s = res;
    int i = 0;
    while (i < (int) s.size() and s[i] == '0') ++i;
    s = s.substr(i);
    return *this;
  }
  Bint& operator%=(const Bint& r) { return *this -= *this / r * r; }
  Bint& operator+=(const Bint& r) {
    auto t = r.s;
    reverse(begin(s), end(s));
    reverse(begin(t), end(t));
    while (s.size() < t.size()) s += '0';
    while (t.size() < s.size()) t += '0';
    s += '0', t += '0';
    if (neg == r.neg) {
      int c = 0;
      for (int i = 0; i < (int) s.size(); ++i) {
        if ((s[i] += t[i] - '0' + c) > '9') {
          s[i] -= 10;
          c = 1;
        } else c = 0;
      }
    } else {
      if (neg) swap(s, t);
      s.back() = '1';
      int c = 0;
      for (int i = 0; i < (int) s.size(); ++i) {
        if ((s[i] -= t[i] - '0' + c) < '0') {
          s[i] += 10;
          c = 1;
        } else c = 0;
      }
      if (neg = s.back() == '0') {
        int i = 0;
        while (s[i] == '0') ++i;
        s[i] = '0' + 10 - (s[i] - '0');
        while (++i < (int) s.size() - 1) s[i] = '9' - (s[i] - '0');
      } else s.back() = '0';
    }
    while (s.size() > 1 and s.back() == '0') s.pop_back();
    reverse(begin(s), end(s));
    return *this;
  }
  Bint& operator-=(const Bint& r) { return *this += -r; }
  template<class Z> friend Bint operator*(Z l, const Bint& r) { return Bint(l) *= r; }
  template<class Z> friend Bint operator/(Z l, const Bint& r) { return Bint(l) /= r; }
  template<class Z> friend Bint operator%(Z l, const Bint& r) { return Bint(l) %= r; }
  template<class Z> friend Bint operator+(Z l, const Bint& r) { return Bint(l) += r; }
  template<class Z> friend Bint operator-(Z l, const Bint& r) { return Bint(l) -= r; }
  friend ostream& operator<<(ostream& os, const Bint& r) { if (r.neg) os << '-'; return os << r.s; }
  friend istream& operator>>(istream& is, Bint& r) { string x; is >> x; r = x; return is; }
  template<class Z> friend bool operator==(Z l, const Bint& r) { return Bint(l) == r; }
  template<class Z> friend bool operator!=(Z l, const Bint& r) { return !(l == r); }
};

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  int k = 1, s = 0;
  while (true) {
    s += (k - 1) * (k - 2) / 2 + 1;
    if (n <= s) break;
    ++k;
  }
  s -= (k - 1) * (k - 2) / 2 + 1;
  n -= s + 1;
  int i;
  for (i = k - 2; i > 0; --i) {
    if (n < i) break;
    n -= i;
  }

  V<string> a;
  a.push_back(string(k, '1'));
  int x = k - 1 - i;
  for (int z = 1; z <= k - 2; ++z) {
    int y = k - x - z;
    if (y <= 0) continue;
    auto s = string(x, '1') + string(y, '0') + string(z, '1');
    a.push_back(s);
  }
  sort(begin(a), end(a));

  auto str = a[n];
  reverse(begin(str), end(str));
  Bint res, c = 1;
  for (int i = 0; i < k; ++i) {
    if (str[i] == '1') {
      res += c;
    }
    c += c;
  }
  cout << res << '\n';
}

yukicoder

結果

テストケース

ソースコード