#948476 (C++23) No.2600 Avator Height

• 問題: No.2600 Avator Height
• ユーザー: Re0denX
• 提出日時: 2024-02-06 23:37:05
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 371 ms / 2,000 ms
• コード長: 7,908 bytes
• コンパイル時間: 3,986 ms
• コンパイル使用メモリ: 245,696 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-28 12:18:28
• 合計ジャッジ時間: 13,304 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	3 ms; 5,248 KB
testcase_01	AC	309 ms; 5,376 KB
testcase_02	AC	302 ms; 5,376 KB
testcase_03	AC	301 ms; 5,376 KB
testcase_04	AC	301 ms; 5,376 KB
testcase_05	AC	300 ms; 5,376 KB
testcase_06	AC	303 ms; 5,376 KB
testcase_07	AC	315 ms; 5,376 KB
testcase_08	AC	308 ms; 5,376 KB
testcase_09	AC	316 ms; 5,376 KB
testcase_10	AC	323 ms; 5,376 KB
testcase_11	AC	323 ms; 5,376 KB
testcase_12	AC	332 ms; 5,376 KB
testcase_13	AC	313 ms; 5,376 KB
testcase_14	AC	308 ms; 5,376 KB
testcase_15	AC	308 ms; 5,376 KB
testcase_16	AC	371 ms; 5,376 KB
testcase_17	AC	370 ms; 5,376 KB
testcase_18	AC	322 ms; 5,376 KB
testcase_19	AC	297 ms; 5,376 KB
testcase_20	AC	301 ms; 5,376 KB
testcase_21	AC	313 ms; 5,376 KB
testcase_22	AC	306 ms; 5,376 KB
testcase_23	AC	312 ms; 5,376 KB
testcase_24	AC	268 ms; 5,376 KB
testcase_25	AC	299 ms; 5,376 KB

ソースコード

#include <bits/stdc++.h>

using namespace std;
#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) 42
#endif  // LOCAL

struct ChronoTimer {
  std::chrono::high_resolution_clock::time_point st;

  ChronoTimer() { reset(); }

  void reset() { st = std::chrono::high_resolution_clock::now(); }

  std::chrono::milliseconds::rep elapsed() {
    auto ed = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::milliseconds>(ed - st)
        .count();
  }
};

/**
 * @brief Scanner(高速入力)
 */
struct Scanner {
 public:
  explicit Scanner(FILE *fp) : fp(fp) {}

  template <typename T, typename... E>
  void read(T &t, E &...e) {
    read_single(t);
    read(e...);
  }

 private:
  static constexpr size_t line_size = 1 << 16;
  static constexpr size_t int_digits = 20;
  char line[line_size + 1] = {};
  FILE *fp = nullptr;
  char *st = line;
  char *ed = line;

  void read() {}

  static inline bool is_space(char c) { return c <= ' '; }

  void reread() {
    ptrdiff_t len = ed - st;
    memmove(line, st, len);
    char *tmp = line + len;
    ed = tmp + fread(tmp, 1, line_size - len, fp);
    *ed = 0;
    st = line;
  }

  void skip_space() {
    while (true) {
      if (st == ed) reread();
      while (*st && is_space(*st)) ++st;
      if (st != ed) return;
    }
  }

  template <typename T, enable_if_t<is_integral<T>::value, int> = 0>
  void read_single(T &s) {
    skip_space();
    if (st + int_digits >= ed) reread();
    bool neg = false;
    if (is_signed<T>::value && *st == '-') {
      neg = true;
      ++st;
    }
    typename make_unsigned<T>::type y = *st++ - '0';
    while (*st >= '0') {
      y = 10 * y + *st++ - '0';
    }
    s = (neg ? -y : y);
  }

  template <typename T, enable_if_t<is_same<T, string>::value, int> = 0>
  void read_single(T &s) {
    s = "";
    skip_space();
    while (true) {
      char *base = st;
      while (*st && !is_space(*st)) ++st;
      s += string(base, st);
      if (st != ed) return;
      reread();
    }
  }

  template <typename T>
  void read_single(vector<T> &s) {
    for (auto &d : s) read(d);
  }
};

/**
 * @brief Printer(高速出力)
 */
struct Printer {
 public:
  explicit Printer(FILE *fp) : fp(fp) {}

  ~Printer() { flush(); }

  template <bool f = false, typename T, typename... E>
  void write(const T &t, const E &...e) {
    if (f) write_single(' ');
    write_single(t);
    write<true>(e...);
  }

  template <typename... T>
  void writeln(const T &...t) {
    write(t...);
    write_single('\n');
  }

  void flush() {
    fwrite(line, 1, st - line, fp);
    st = line;
  }

 private:
  FILE *fp = nullptr;
  static constexpr size_t line_size = 1 << 16;
  static constexpr size_t int_digits = 20;
  char line[line_size + 1] = {};
  char *st = line;

  template <bool f = false>
  void write() {}

  void write_single(const char &t) {
    if (st + 1 >= line + line_size) flush();
    *st++ = t;
  }

  template <typename T, enable_if_t<is_integral<T>::value, int> = 0>
  void write_single(T s) {
    if (st + int_digits >= line + line_size) flush();
    st += to_chars(st, st + int_digits, s).ptr - st;
  }

  void write_single(const string &s) {
    for (auto &c : s) write_single(c);
  }

  void write_single(const char *s) {
    while (*s != 0) write_single(*s++);
  }

  template <typename T>
  void write_single(const vector<T> &s) {
    for (size_t i = 0; i < s.size(); i++) {
      if (i) write_single(' ');
      write_single(s[i]);
    }
  }
};

Scanner scanner = Scanner(stdin);
Printer printer = Printer(stdout);

void flush() { printer.flush(); }
void print() { printer.write('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
  printer.write(head);
  if (sizeof...(Tail)) printer.write(' ');
  print(forward<Tail>(tail)...);
}

void read() {}
template <class Head, class... Tail>
void read(Head &head, Tail &...tail) {
  scanner.read(head);
  read(tail...);
}

template <typename T>
T mod_inv_in_range(T a, T m) {
  // assert(0 <= a && a < m);
  T x = a, y = m;
  // coeff of a in x and y
  T vx = 1, vy = 0;
  while (x) {
    T k = y / x;
    y %= x;
    vy -= k * vx;
    std::swap(x, y);
    std::swap(vx, vy);
  }
  assert(y == 1);
  return vy < 0 ? m + vy : vy;
}

template <typename T>
struct extended_gcd_result {
  T gcd;
  T coeff_a, coeff_b;
};
template <typename T>
extended_gcd_result<T> extended_gcd(T a, T b) {
  T x = a, y = b;
  // coeff of a and b in x and y
  T ax = 1, ay = 0;
  T bx = 0, by = 1;
  while (x) {
    T k = y / x;
    y %= x;
    ay -= k * ax;
    by -= k * bx;
    std::swap(x, y);
    std::swap(ax, ay);
    std::swap(bx, by);
  }
  return {y, ay, by};
}

template <typename T>
T mod_inv(T a, T m) {
  a %= m;
  a = a < 0 ? a + m : a;
  return mod_inv_in_range(a, m);
}

template <int MOD_>
struct modnum {
  static constexpr int MOD = MOD_;
  static_assert(MOD_ > 0, "MOD must be positive");

 private:
  int v;

 public:
  modnum() : v(0) {}
  modnum(int64_t v_) : v(int(v_ % MOD)) {
    if (v < 0) v += MOD;
  }
  explicit operator int() const { return v; }
  friend std::ostream& operator<<(std::ostream& out, const modnum& n) {
    return out << int(n);
  }
  friend std::istream& operator>>(std::istream& in, modnum& n) {
    int64_t v_;
    in >> v_;
    n = modnum(v_);
    return in;
  }

  friend bool operator==(const modnum& a, const modnum& b) {
    return a.v == b.v;
  }
  friend bool operator!=(const modnum& a, const modnum& b) {
    return a.v != b.v;
  }

  modnum inv() const {
    modnum res;
    res.v = mod_inv_in_range(v, MOD);
    return res;
  }
  friend modnum inv(const modnum& m) { return m.inv(); }
  modnum neg() const {
    modnum res;
    res.v = v ? MOD - v : 0;
    return res;
  }
  friend modnum neg(const modnum& m) { return m.neg(); }

  modnum operator-() const { return neg(); }
  modnum operator+() const { return modnum(*this); }

  modnum& operator++() {
    v++;
    if (v == MOD) v = 0;
    return *this;
  }
  modnum& operator--() {
    if (v == 0) v = MOD;
    v--;
    return *this;
  }
  modnum& operator+=(const modnum& o) {
    v -= MOD - o.v;
    v = (v < 0) ? v + MOD : v;
    return *this;
  }
  modnum& operator-=(const modnum& o) {
    v -= o.v;
    v = (v < 0) ? v + MOD : v;
    return *this;
  }
  modnum& operator*=(const modnum& o) {
    v = int(int64_t(v) * int64_t(o.v) % MOD);
    return *this;
  }
  modnum& operator/=(const modnum& o) { return *this *= o.inv(); }

  friend modnum operator++(modnum& a, int) {
    modnum r = a;
    ++a;
    return r;
  }
  friend modnum operator--(modnum& a, int) {
    modnum r = a;
    --a;
    return r;
  }
  friend modnum operator+(const modnum& a, const modnum& b) {
    return modnum(a) += b;
  }
  friend modnum operator-(const modnum& a, const modnum& b) {
    return modnum(a) -= b;
  }
  friend modnum operator*(const modnum& a, const modnum& b) {
    return modnum(a) *= b;
  }
  friend modnum operator/(const modnum& a, const modnum& b) {
    return modnum(a) /= b;
  }
};

template <typename T>
T pow(T a, long long b) {
  assert(b >= 0);
  T r = 1;
  while (b) {
    if (b & 1) r *= a;
    b >>= 1;
    a *= a;
  }
  return r;
}
using num = modnum<998244353>;

constexpr int _ = 200010;
num R[_], E[_];

int main(int, char **) {
#ifdef LOCAL
  ChronoTimer chrono;
  freopen("/home/user/acm/competitve/src/input.txt", "r", stdin);
  freopen("/home/user/acm/competitve/src/output.txt", "w", stdout);
#endif
  std::cout << fixed << setprecision(12);
  R[1] = R[2] = 1;
  E[1] = 1, E[2] = 3;

  for (auto i : views::iota(3, _)) {
    R[i] = R[i - 1] + R[i - 2];
    E[i] = E[i - 2] + E[i - 1];
  }

  int Q; 
  std::cin >> Q;
  while (Q--) {
    int N; 
    std::cin >> N;

    auto sq = [] (num x) {
      return x * x;
    };

    num ans = sq(R[N]) * 5 - sq(E[N]);
    cout << ans << "\n";
  }

#ifdef LOCAL
  print("\nRunning Time:", chrono.elapsed(), "ms");
#endif
}