競プロ日記

コード
行列累乗
https://atcoder.jp/contests/abc129/submissions/7196508
ダブリング①
https://atcoder.jp/contests/abc129/submissions/7196517
ダブリング②
https://atcoder.jp/contests/abc129/submissions/7196857


しんどい！！！
E問題も相当かかったしABC129は強敵だった。
E問題は単純に桁DPを知るだけで終わったから特に書くことはないが、これは本当にしんどかった。
最初尋常じゃない定義域も相まって解き方の検討がつかなかったが、解説を読んでこういうのも漸化式で解けるのかと感心した。

行列累乗

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(V, v) for (auto &&V : v)
#define all(x) (x).begin(), (x).end()
constexpr int INF = 1 << 30;
constexpr long long INFL = 1LL << 62;
constexpr int MOD = 1e9 + 7;
constexpr double EPS = 1e-9;
using lint = long long;

using namespace std;

class VariableModInt {
  long long n_;
  static long long &mod() {
    static long long mod_ = 1;
    return mod_;
  }

  public:
  VariableModInt(const long long num = 0) : n_(num % get_mod()) {}
  const long long &value() const { return n_; }
  bool operator==(const VariableModInt &r) const { return this->n_ == r.n_; }
  bool operator==(const long long &r) const { return this->n_ == r; }
  bool operator!=(const VariableModInt &r) const { return this->n_ != r.n_; }
  bool operator!=(const long long &r) const { return this->n_ != r; }
  bool operator<(const VariableModInt &r) const { return this->n_ < r.n_; }
  bool operator<(const long long &r) const { return this->n_ < r; }
  bool operator>(const VariableModInt &r) const { return this->n_ > r.n_; }
  bool operator>(const long long &r) const { return this->n_ > r; }
  bool operator<=(const VariableModInt &r) const { return this->n_ <= r.n_; }
  bool operator<=(const long long &r) const { return this->n_ <= r; }
  bool operator>=(const VariableModInt &r) const { return this->n_ >= r.n_; }
  bool operator>=(const long long &r) const { return this->n_ >= r; }
  VariableModInt operator+(const VariableModInt &r) const { return VariableModInt(*this) += r; }
  VariableModInt operator-(const VariableModInt &r) const { return VariableModInt(*this) -= r; }
  VariableModInt operator*(const VariableModInt &r) const { return VariableModInt(*this) *= r; }
  VariableModInt operator/(const VariableModInt &r) const { return VariableModInt(*this) /= r; }
  VariableModInt operator+(const long long &r) const { return VariableModInt(*this) += VariableModInt(r); }
  VariableModInt operator-(const long long &r) const { return VariableModInt(*this) -= VariableModInt(r); }
  VariableModInt operator*(const long long &r) const { return VariableModInt(*this) *= VariableModInt(r); }
  VariableModInt operator/(const long long &r) const { return VariableModInt(*this) /= VariableModInt(r); }
  friend VariableModInt operator+(const long long &l, const VariableModInt &r) { return VariableModInt(l) += r; }
  friend VariableModInt operator-(const long long &l, const VariableModInt &r) { return VariableModInt(l) -= r; }
  friend VariableModInt operator*(const long long &l, const VariableModInt &r) { return VariableModInt(l) *= r; }
  friend VariableModInt operator/(const long long &l, const VariableModInt &r) { return VariableModInt(l) /= r; }
  VariableModInt &operator++() { return *this += 1; }
  VariableModInt &operator--() { return *this -= 1; }
  VariableModInt &operator+=(const VariableModInt &r) {
    n_ += r.n_;
    if (n_ >= get_mod()) n_ -= get_mod();
    return *this;
  }
  VariableModInt &operator-=(const VariableModInt &r) {
    if (n_ < r.n_) n_ += get_mod();
    n_ -= r.n_;
    return *this;
  }
  VariableModInt &operator*=(const VariableModInt &r) {
    n_ = n_ * r.n_ % get_mod();
    return *this;
  }
  VariableModInt &operator/=(VariableModInt r) {
    long long exp = get_mod() - 2;
    while (exp) {
      if (exp & 2) *this *= r;
      r *= r;
      exp /= 2;
    }
    return *this;
  }
  static void set_mod(const long long mod_num) { mod() = mod_num; }
  static long long get_mod() { return mod(); }
  explicit operator int() const { return n_; }
  explicit operator long long() const { return n_; }
  explicit operator double() const { return n_; }
  friend std::istream &operator>>(std::istream &is, VariableModInt &r) {
    is >> r.n_;
    r.n_ %= r.get_mod();
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, const VariableModInt &r) { return os << r.n_; }
};

template 
class Matrix {
  int h_, w_;
  std::vector<std::vector> mat_;

  public:
  Matrix(void) {}
  Matrix(size_t n) : h_(n), w_(n), mat_(h_, std::vector(w_)) {}
  Matrix(size_t height, size_t width) : h_(height), w_(width), mat_(h_, std::vector(w_)) {}
  Matrix(size_t height, size_t width, T initial) : h_(height), w_(width), mat_(h_, std::vector(w_, initial)) {}
  Matrix(std::initializer_list<std::initializer_list> list_2d) : h_(list_2d.size()), w_(list_2d.begin()->size()), mat_(list_2d.begin(), list_2d.end()) {
    for (const auto &list : list_2d) assert(w_ == list.size());
  }
  const std::vector &operator[](size_t k) const { return mat_[k]; }
  std::vector &operator[](size_t k) { return mat_[k]; }
  Matrix operator+(const Matrix &rmat) const { return (Matrix(*this) += rmat); }
  Matrix operator-(const Matrix &rmat) const { return (Matrix(*this) -= rmat); }
  Matrix operator*(const Matrix &rmat) const { return (Matrix(*this) *= rmat); }
  Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); }
  Matrix operator*(const T &n) const { return (Matrix(*this) *= n); }
  friend Matrix operator*(const T &t, const Matrix &rmat) { return (Matrix(rmat) *= t); }
  Matrix &operator+=(const Matrix &rmat) {
    assert(h_ == rmat.h_ && w_ == rmat.w_);
    for (int i = 0; i < h_; ++i) {
      for (int j = 0; j < w_; ++j) {
        mat_[i][j] += rmat[i][j];
      }
    }
    return *this;
  }
  Matrix &operator-=(const Matrix &rmat) {
    assert(h_ == rmat.h_ && w_ == rmat.w_);
    for (int i = 0; i < h_; ++i) {
      for (int j = 0; j < w_; ++j) {
        mat_[i][j] -= rmat[i][j];
      }
    }
    return *this;
  }
  Matrix &operator*=(const Matrix &rmat) {
    assert(w_ == rmat.h_);
    std::vector<std::vector> nmat(h_, std::vector(rmat.w_));
    for (int i = 0; i < h_; ++i) {
      for (int k = 0; k < w_; ++k) {
        for (int j = 0; j < rmat.w_; ++j) {
          nmat[i][j] += mat_[i][k] * rmat[k][j];
        }
      }
    }
    mat_.swap(nmat);
    w_ = rmat.w_;
    return *this;
  }
  Matrix &operator*=(const int n) {
    for (int i = 0; i < h_; ++i) {
      for (int j = 0; j < w_; ++j) {
        mat_[i][j] *= n;
      }
    }
    return *this;
  }
  Matrix &operator^=(long long k) {
    assert(h_ == w_);
    Matrix imat(h_);
    for (int i = 0; i < h_; ++i) imat[i][i] = 1;
    while (k > 0) {
      if (k & 1) imat *= *this;
      *this *= *this;
      k >>= 1;
    }
    mat_.swap(imat.mat_);
    return *this;
  }
  int height(void) { return h_; }
  int width(void) { return w_; }
  T max_value() {
    T maxi = *std::max_element(mat_[0].begin(), mat_[0].end());
    for (int i = 1; i < h_; ++i) maxi = std::max(maxi, *std::max_element(mat_[i].begin(), mat_[i].end()));
    return maxi;
  }
  T min_value() {
    T mini = *std::min_element(mat_[0].begin(), mat_[0].end());
    for (int i = 1; i < h_; ++i) mini = std::min(mini, *std::min_element(mat_[i].begin(), mat_[i].end()));
    return mini;
  }
  friend ostream &operator<<(ostream &os, Matrix &mat) {
    int digit = std::log10((double)mat.max_value()) + 2;
    for (int i = 0; i < mat.h_; ++i) {
      os << "[";
      for (int j = 0; j < mat.w_; ++j) {
        os << std::setw(digit) << mat[i][j] << (j + 1 == mat.w_ ? " ]\n" : ",");
      }
    }
    return os;
  }
  // External
  Matrix transpose(void);
  T determinant(void);
  T rational_determinant(void);
};

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);

  lint l, a, b, m;
  cin >> l >> a >> b >> m;
  vector k;
  k.push_back(0);
  lint x = 1;
  rep1 (i, 18) {
    x *= 10;
    if (x - a < 0) {
      k.push_back(0);
    } else {
      lint t = min((x - 1 - a) / b + 1, l);
      k.push_back(t);
      if (t == l) break;
    }
  }
  VariableModInt::set_mod(m);
  Matrix product_mat{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
  rrep1(i, k.size() - 1) {
    lint len = k[i] - k[i - 1];
    if (len <= 0) continue;
    Matrix mat{{1, 0, b}, {1, x, 0}, {0, 0, 1}};
    mat ^= len;
    product_mat *= mat;
    x /= 10;
  }
  Matrix init{{a}, {0}, {1}};
  product_mat *= init;
  cout << product_mat[1][0] << endl;
  return 0;
}

行列ってこういう使い方ができるのかぁという感想。
連立方程式を行列にして～みたいな計算も学生時代一瞬で終わってしまったからほぼ記憶になかった。
そもそも漸化式を作ることすら発想になかったので、もし漸化式を作っていたら蟻本の記憶で思いついた可能性もなきにしもあらず・・・。
こういう線形変換をアフィン変換というらしいけど初耳。
同次変換行列は勉強した記憶があるのでそっちのイメージのほうが強い。
実装に取り掛かってみるととても簡単。
行列の実装が相当しんどかった。
今回使わなかった行列式を有理数の演算で実装したのが悪い。

ダブリング

①

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(V, v) for (auto &&V : v)
#define all(x) (x).begin(), (x).end()
constexpr int INF = 1 << 30;
constexpr long long INFL = 1LL << 62;
constexpr int MOD = 1e9 + 7;
constexpr double EPS = 1e-9;
using lint = long long;

using namespace std;

class VariableModInt {
  long long n_;
  static long long &mod() {
    static long long mod_ = 1;
    return mod_;
  }

  public:
  VariableModInt(const long long num = 0) : n_(num % get_mod()) {}
  const long long &value() const { return n_; }
  bool operator==(const VariableModInt &r) const { return this->n_ == r.n_; }
  bool operator==(const long long &r) const { return this->n_ == r; }
  bool operator!=(const VariableModInt &r) const { return this->n_ != r.n_; }
  bool operator!=(const long long &r) const { return this->n_ != r; }
  bool operator<(const VariableModInt &r) const { return this->n_ < r.n_; }
  bool operator<(const long long &r) const { return this->n_ < r; }
  bool operator>(const VariableModInt &r) const { return this->n_ > r.n_; }
  bool operator>(const long long &r) const { return this->n_ > r; }
  bool operator<=(const VariableModInt &r) const { return this->n_ <= r.n_; }
  bool operator<=(const long long &r) const { return this->n_ <= r; }
  bool operator>=(const VariableModInt &r) const { return this->n_ >= r.n_; }
  bool operator>=(const long long &r) const { return this->n_ >= r; }
  VariableModInt operator+(const VariableModInt &r) const { return VariableModInt(*this) += r; }
  VariableModInt operator-(const VariableModInt &r) const { return VariableModInt(*this) -= r; }
  VariableModInt operator*(const VariableModInt &r) const { return VariableModInt(*this) *= r; }
  VariableModInt operator/(const VariableModInt &r) const { return VariableModInt(*this) /= r; }
  VariableModInt operator+(const long long &r) const { return VariableModInt(*this) += VariableModInt(r); }
  VariableModInt operator-(const long long &r) const { return VariableModInt(*this) -= VariableModInt(r); }
  VariableModInt operator*(const long long &r) const { return VariableModInt(*this) *= VariableModInt(r); }
  VariableModInt operator/(const long long &r) const { return VariableModInt(*this) /= VariableModInt(r); }
  friend VariableModInt operator+(const long long &l, const VariableModInt &r) { return VariableModInt(l) += r; }
  friend VariableModInt operator-(const long long &l, const VariableModInt &r) { return VariableModInt(l) -= r; }
  friend VariableModInt operator*(const long long &l, const VariableModInt &r) { return VariableModInt(l) *= r; }
  friend VariableModInt operator/(const long long &l, const VariableModInt &r) { return VariableModInt(l) /= r; }
  VariableModInt &operator++() { return *this += 1; }
  VariableModInt &operator--() { return *this -= 1; }
  VariableModInt &operator+=(const VariableModInt &r) {
    n_ += r.n_;
    if (n_ >= get_mod()) n_ -= get_mod();
    return *this;
  }
  VariableModInt &operator-=(const VariableModInt &r) {
    if (n_ < r.n_) n_ += get_mod();
    n_ -= r.n_;
    return *this;
  }
  VariableModInt &operator*=(const VariableModInt &r) {
    n_ = n_ * r.n_ % get_mod();
    return *this;
  }
  VariableModInt &operator/=(VariableModInt r) {
    long long exp = get_mod() - 2;
    while (exp) {
      if (exp & 2) *this *= r;
      r *= r;
      exp /= 2;
    }
    return *this;
  }
  static void set_mod(const long long mod_num) { mod() = mod_num; }
  static long long get_mod() { return mod(); }
  explicit operator int() const { return n_; }
  explicit operator long long() const { return n_; }
  explicit operator double() const { return n_; }
  friend std::istream &operator>>(std::istream &is, VariableModInt &r) {
    is >> r.n_;
    r.n_ %= r.get_mod();
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, const VariableModInt &r) { return os << r.n_; }
};

using mint = VariableModInt;

mint f(lint i, mint &tenk, lint ten) {
  static map<tuple<lint, lint>, mint> memory;
  if (memory.find(tuple<lint, lint>(i, ten)) != memory.end()) return memory[tuple<lint, lint>(i, ten)];
  if (i == 0) return 0;
  mint ft;
  if (i & 1) {
    ft = f(i - 1, tenk, ten);
    ft = ft * ten + 1;
    tenk *= ten;
  } else {
    ft = f(i / 2, tenk, ten);
    ft = ft * (tenk + 1);
    tenk *= tenk;
  }
  return memory[tuple<lint, lint>(i, ten)] = ft;
}

mint g(lint i, mint &tenk, lint ten, mint &B, lint plusi) {
  if (i == 0) return 0;
  mint gt;
  if (i & 1) {
    lint bi = i - 1;
    gt = g(bi, tenk, ten, B, plusi);
    gt = gt * ten + B * (plusi + bi);
    tenk *= ten;
  } else {
    lint bi = i / 2;
    mint ctenk(tenk);
    gt = g(bi, tenk, ten, B, plusi);
    gt = gt * (tenk + 1) + B * bi * f(bi, ctenk, ten);
    tenk *= tenk;
  }
  return gt;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);

  lint l, a, b, m;
  cin >> l >> a >> b >> m;
  vector k;
  k.push_back(0);
  lint x = 1;
  rep1 (i, 18) {
    x *= 10;
    if (x - a < 0) {
      k.push_back(0);
    } else {
      lint t = (x - 1 - a) / b + 1;
      if (t > l) {
        k.push_back(l);
        break;
      }
      k.push_back(t);
    }
  }
  mint::set_mod(m);
  mint sum = 0;
  x = 1;
  mint A = a, B = b;
  rep1 (i, k.size() - 1) {
    x *= 10;
    lint len = k[i] - k[i - 1];
    if (len <= 0) continue;
    mint fk = 1, gk = 1;
    auto F = f(len, fk, x);
    auto G = g(len, gk, x, B, k[i - 1]);
    sum = sum * fk + A * F + G;
  }
  cout << sum << endl;
  return 0;
}

②

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(V, v) for (auto &&V : v)
#define all(x) (x).begin(), (x).end()
constexpr int INF = 1 << 30;
constexpr long long INFL = 1LL << 62;
constexpr int MOD = 1e9 + 7;
constexpr double EPS = 1e-9;
using lint = long long;

using namespace std;

class VariableModInt {
  long long n_;
  static long long &mod() {
    static long long mod_ = 1;
    return mod_;
  }

  public:
  VariableModInt(const long long num = 0) : n_(num % get_mod()) {}
  const long long &value() const { return n_; }
  bool operator==(const VariableModInt &r) const { return this->n_ == r.n_; }
  bool operator==(const long long &r) const { return this->n_ == r; }
  bool operator!=(const VariableModInt &r) const { return this->n_ != r.n_; }
  bool operator!=(const long long &r) const { return this->n_ != r; }
  bool operator<(const VariableModInt &r) const { return this->n_ < r.n_; }
  bool operator<(const long long &r) const { return this->n_ < r; }
  bool operator>(const VariableModInt &r) const { return this->n_ > r.n_; }
  bool operator>(const long long &r) const { return this->n_ > r; }
  bool operator<=(const VariableModInt &r) const { return this->n_ <= r.n_; }
  bool operator<=(const long long &r) const { return this->n_ <= r; }
  bool operator>=(const VariableModInt &r) const { return this->n_ >= r.n_; }
  bool operator>=(const long long &r) const { return this->n_ >= r; }
  VariableModInt operator+(const VariableModInt &r) const { return VariableModInt(*this) += r; }
  VariableModInt operator-(const VariableModInt &r) const { return VariableModInt(*this) -= r; }
  VariableModInt operator*(const VariableModInt &r) const { return VariableModInt(*this) *= r; }
  VariableModInt operator/(const VariableModInt &r) const { return VariableModInt(*this) /= r; }
  VariableModInt operator+(const long long &r) const { return VariableModInt(*this) += VariableModInt(r); }
  VariableModInt operator-(const long long &r) const { return VariableModInt(*this) -= VariableModInt(r); }
  VariableModInt operator*(const long long &r) const { return VariableModInt(*this) *= VariableModInt(r); }
  VariableModInt operator/(const long long &r) const { return VariableModInt(*this) /= VariableModInt(r); }
  friend VariableModInt operator+(const long long &l, const VariableModInt &r) { return VariableModInt(l) += r; }
  friend VariableModInt operator-(const long long &l, const VariableModInt &r) { return VariableModInt(l) -= r; }
  friend VariableModInt operator*(const long long &l, const VariableModInt &r) { return VariableModInt(l) *= r; }
  friend VariableModInt operator/(const long long &l, const VariableModInt &r) { return VariableModInt(l) /= r; }
  VariableModInt &operator++() { return *this += 1; }
  VariableModInt &operator--() { return *this -= 1; }
  VariableModInt &operator+=(const VariableModInt &r) {
    n_ += r.n_;
    if (n_ >= get_mod()) n_ -= get_mod();
    return *this;
  }
  VariableModInt &operator-=(const VariableModInt &r) {
    if (n_ < r.n_) n_ += get_mod();
    n_ -= r.n_;
    return *this;
  }
  VariableModInt &operator*=(const VariableModInt &r) {
    n_ = n_ * r.n_ % get_mod();
    return *this;
  }
  VariableModInt &operator/=(VariableModInt r) {
    long long exp = get_mod() - 2;
    while (exp) {
      if (exp & 2) *this *= r;
      r *= r;
      exp /= 2;
    }
    return *this;
  }
  static void set_mod(const long long mod_num) { mod() = mod_num; }
  static long long get_mod() { return mod(); }
  explicit operator int() const { return n_; }
  explicit operator long long() const { return n_; }
  explicit operator double() const { return n_; }
  friend std::istream &operator>>(std::istream &is, VariableModInt &r) {
    is >> r.n_;
    r.n_ %= r.get_mod();
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, const VariableModInt &r) { return os << r.n_; }
};

template 
T power(T x, long long n) {
  T ret = 1;
  while (n) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
}

using mint = VariableModInt;

mint pow_10(lint k) {
  static unordered_map<lint, mint> memory{{0, 1}};
  if (memory.find(k) != memory.end()) return memory[k];
  if (k & 1) {
    return memory[k] = pow_10(k - 1) * 10;
  } else {
    mint x = pow_10(k / 2);
    return memory[k] = x * x;
  }
}

mint f(lint i, int k) {
  static map<tuple<lint, int>, mint> memory;
  if (memory.find(pair<lint, int>(i, k)) != memory.end()) return memory[pair<lint, int>(i, k)];
  if (i == 0) return 0;
  if (i & 1) {
    return memory[pair<lint, int>(i, k)] = f(i - 1, k) * pow_10(k) + 1;
  } else {
    return memory[pair<lint, int>(i, k)] = f(i / 2, k) * (pow_10(k * (i / 2)) + 1);
  }
}

mint g(lint i, int k, lint plusi, mint &B) {
  if (i == 0) return 0;
  mint gt;
  if (i & 1) {
    return g(i - 1, k, plusi, B) * pow_10(k) + B * (plusi + i - 1);
  } else {
    return g(i / 2, k, plusi, B) * (pow_10(k * (i / 2)) + 1) + B * (i / 2) * f(i / 2, k);
  }
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);

  lint l, a, b, m;
  cin >> l >> a >> b >> m;
  vector k;
  k.push_back(0);
  lint x = 1;
  rep1 (i, 18) {
    x *= 10;
    if (x - a < 0) {
      k.push_back(0);
    } else {
      lint t = min((x - 1 - a) / b + 1, l);
      k.push_back(t);
      if (t == l) break;
    }
  }
  mint::set_mod(m);
  mint sum = 0, A = a, B = b;
  rep1 (i, k.size() - 1) {
    lint len = k[i] - k[i - 1];
    if (len <= 0) continue;
    sum = sum * power(pow_10(len), i) + A * f(len, i) + g(len, i, k[i - 1], B);
  }
  cout << sum << endl;
  return 0;
}

結局行列とか整数とかの繰り返し二乗法もやってることはダブリングじゃないのか？
と最初思ったが最終的に、「保持する情報が少ないために簡単に実装できるダブリングの一種」という認識になった。
今回の問題も最初関数のダブリングを計算する際、ビットの最下位が立っているかどうかの再帰を使わずループで回す形で実装しようと考えた。
しかし、ダブリングの計算にインデックスがいるのだが、どう考えてもこの方法だと正しいインデックスを得られない。
インデックスは0から上がっていくのに対し、この二乗法で計算されるインデックスはMAXから下がっていく方法だ。
どこで1加えてどこで2倍して・・・をどうやって保持しようか。
そう考えて解説のコードを見てみると、全員が再帰で実装している。
やはりダブリングは再帰でやるのがセオリーなのだろうか。
このことから、繰り返し二乗法は前述した「保持する情報が少ないために簡単に実装できるダブリングの一種」という結論に至った。

ダブリングの疑問は解決されたところで、実装がとにかくしんどかった。
追っていく変数が多すぎてどこでミスるか分かったものじゃない。
定義域がやたらと大きいことから、保持する情報を増やしてなるべく計算量を落とそうと思ったのだが、それが大きな間違いだった。
①が最初のコード、②が保持する情報を減らそうと頑張ったコードである。
10の自乗の状態を保存しておこうとしたのだが、それくらい計算しても全然問題なかった。
さっき計算したらlog(10^18)すら100に満たないんだな。
ちなみに関数内で値を保存するためのstatic変数を学生時代ぶりに使ったのがちょっとノスタルジック。
それでも色々保存するようにしたが、結局①も②も実行時間は2msで、最初から保持する情報を減らしておけばもうちょっとしんどくなかったかもしれない。
このブログでも何度目かのオーダーの把握は大事だなぁ・・・。
実装している最中、他のダブリング問題が出てきても解ける気がしておらず、完全に苦手問題なんだなと思っていたが、追うべき変数を減らすことを意識したら行けるかもしれない。

以下今回のしんどかったポイント。

しんどかったポイント①
行列演算クラスMatrixの実装
行列式の有理式での計算に謎に力を入れたせいですさまじい時間を取られた。

しんどかったポイント②
常にmodを取ってくれる整数値クラスModIntの実装
C++の仕様にちょっと苦労した。
行列の実装に比べると大したこと無い。

しんどかったポイント③
変数の値を追う
保持している情報と変化するポイントが多いのと、その段階での正しい値の計算の難しさと、常にmodを取っていることから、デバッグで変数の値を追うのが相当しんどかった。
後々のことを考えたら、楽できる(変数・情報を減らせる)ところは、苦労して(オーダーを把握するために計算して)でも楽すべきだった。


今週末はABCがあるみたいですね。
今週こそ参加なのです！