結果

問題 No.1136 Four Points Tour
ユーザー cutmdocutmdo
提出日時 2024-12-19 17:31:34
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 5,749 bytes
コンパイル時間 1,230 ms
コンパイル使用メモリ 94,888 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-12-19 17:31:38
合計ジャッジ時間 2,857 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 3 ms
6,820 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 3 ms
6,816 KB
testcase_10 AC 2 ms
6,816 KB
testcase_11 AC 2 ms
6,816 KB
testcase_12 AC 2 ms
6,816 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 2 ms
6,816 KB
testcase_17 AC 2 ms
6,816 KB
testcase_18 AC 1 ms
6,820 KB
testcase_19 AC 2 ms
6,820 KB
testcase_20 AC 1 ms
6,816 KB
testcase_21 AC 2 ms
6,824 KB
01_Sample03_evil.txt AC 2 ms
6,820 KB
04_Rnd_large_evil1.txt AC 1 ms
6,816 KB
04_Rnd_large_evil2.txt AC 2 ms
6,816 KB
04_Rnd_large_evil3.txt AC 2 ms
6,816 KB
04_Rnd_large_evil4.txt AC 2 ms
6,816 KB
04_Rnd_large_evil5.txt AC 2 ms
6,816 KB
04_Rnd_large_evil6.txt AC 2 ms
6,820 KB
04_Rnd_large_evil7.txt AC 2 ms
6,816 KB
04_Rnd_large_evil8.txt AC 2 ms
6,820 KB
04_Rnd_large_evil9.txt AC 2 ms
6,816 KB
04_Rnd_large_evil10.txt AC 2 ms
6,816 KB
05_Rnd_huge_evil1.txt AC 2 ms
6,816 KB
05_Rnd_huge_evil2.txt AC 2 ms
6,816 KB
05_Rnd_huge_evil3.txt AC 2 ms
6,820 KB
05_Rnd_huge_evil4.txt AC 2 ms
6,816 KB
05_Rnd_huge_evil5.txt AC 2 ms
6,816 KB
05_Rnd_huge_evil6.txt AC 2 ms
6,820 KB
05_Rnd_huge_evil7.txt AC 2 ms
6,816 KB
99_evil_01.txt AC 2 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define PROBLEM "https://yukicoder.me/problems/no/1136"

#include <iostream>

#include <cassert>
#include <iterator>
#include <iostream>
#include <vector>
namespace mtd {  template <class T>  class Matrix {    int h, w;    std::vector<std::vector<T>> mat;  public:    Matrix(const std::vector<std::vector<T>>& mat)        : h(mat.size()), w(mat[0].size()), mat(mat) {}    inline static auto identity(int size) {      std::vector<std::vector<T>> ret(size, std::vector<T>(size));      for (int i = 0; i < size; ++i) { ret[i][i] = 1; }      return Matrix(ret);    }    auto begin() const { return mat.begin(); }    auto end() const { return mat.end(); }    const auto& operator[](int i) const { return mat[i]; }    auto& operator[](int i) { return mat[i]; }    auto operator*(const Matrix& tgt) const {      assert(w == tgt.h);      std::vector<std::vector<T>> ret(h, std::vector<T>(tgt.w));      for (int i = 0; i < h; ++i)        for (int j = 0; j < tgt.w; ++j) {          for (int k = 0; k < w; ++k) { ret[i][j] += mat[i][k] * tgt[k][j]; }        }      return Matrix(ret);    }    auto pow(long long n) const {      assert(h == w);      auto ret = identity(h);      auto now = *this;      while (n) {        if (n & 1) { ret = ret * now; }        n >>= 1;        now = now * now;      }      return ret;    }  };}  
namespace mtd {  template <class T>  class Math {    const std::vector<T> m_fac;    const std::vector<T> m_finv;    auto constructFac(int s) {      std::vector<T> fac(s);      fac[0] = fac[1] = 1;      for (long long i = 2; i < s; ++i) { fac[i] = fac[i - 1] * i; }      return fac;    }    auto constructInv(int s) {      std::vector<T> finv(s);      finv[s - 1] = 1 / m_fac[s - 1];      for (long long i = s - 2; i >= 0; --i) {        finv[i] = finv[i + 1] * (i + 1);      }      return finv;    }  public:    constexpr Math(long long size = 3 * 1e6)        : m_fac(constructFac(size)), m_finv(constructInv(size)) {}    static constexpr T pow(T a, long long b) {      T ans = 1;      while (b > 0) {        if (b & 1) { ans *= a; }        b >>= 1;        a *= a;      }      return ans;    }    constexpr auto fact(int n) const { return (n < 0) ? 0 : m_fac[n]; }    constexpr auto factInv(int n) const { return (n < 0 ? 0 : m_finv[n]); }    constexpr auto comb(int n, int r) const {      return fact(n) * factInv(r) * factInv(n - r);    }    constexpr auto perm(int n, int r) const { return fact(n) * factInv(n - r); }  };}  
namespace mtd {  template <int MOD, class T = long long>  class ModInt {  public:    T x;    constexpr ModInt(T x) : x(x >= 0 ? x % MOD : MOD + (x % MOD)) {}    constexpr ModInt() : ModInt(0) {}        constexpr auto& operator+=(const ModInt<MOD, T>& m) {      x += m.x;      if (x >= MOD) { x -= MOD; }      return *this;    }    constexpr auto& operator-=(const ModInt<MOD, T>& m) {      x -= m.x;      if (x < 0) { x += MOD; }      return *this;    }    constexpr auto& operator*=(const ModInt<MOD, T>& m) {      x *= m.x;      if (x >= MOD) { x %= MOD; }      return *this;    }    constexpr auto& operator/=(const ModInt<MOD, T>& m) {      x *= mtd::Math<ModInt<MOD, T>>::pow(m.x, MOD - 2).x;      if (x >= MOD) { x %= MOD; }      return *this;    }    constexpr auto operator+(const ModInt<MOD, T>& m) const {      auto t = *this;      t += m;      return t;    }    constexpr auto operator-(const ModInt<MOD, T>& m) const {      auto t = *this;      t -= m;      return t;    }    constexpr auto operator*(const ModInt<MOD, T>& m) const {      auto t = *this;      t *= m;      return t;    }    constexpr auto operator/(const ModInt<MOD, T>& m) const {      auto t = *this;      t /= m;      return t;    }    constexpr auto& operator+=(const T& t) {      return *this += ModInt<MOD, T>(t);    }    constexpr auto& operator-=(const T& t) {      return *this -= ModInt<MOD, T>(t);    }    constexpr auto& operator*=(const T& n) {      return *this *= ModInt<MOD, T>(n);    }    constexpr auto& operator/=(const T& n) {      return *this /= ModInt<MOD, T>(n);    }    constexpr auto operator+(const T& t) const {      return *this + ModInt<MOD, T>(t);    }    constexpr auto operator-(const T& t) const {      return *this - ModInt<MOD, T>(t);    }    constexpr auto operator*(const T& t) const {      return *this * ModInt<MOD, T>(t);    }    constexpr auto operator/(const T& t) const {      return *this / ModInt<MOD, T>(t);    }    constexpr friend auto operator+(const T& t, const ModInt<MOD, T>& m) {      return m + t;    }    constexpr friend auto operator-(const T& t, const ModInt<MOD, T>& m) {      return -m + t;    }    constexpr friend auto operator*(const T& t, const ModInt<MOD, T>& m) {      return m * t;    }    constexpr friend auto operator/(const T& t, const ModInt<MOD, T>& m) {      return ModInt<MOD, T>(1) / m * t;    }        constexpr auto operator-() const { return ModInt<MOD, T>(0 - x); }        constexpr auto operator!=(const ModInt<MOD, T>& m) const {      return x != m.x;    }    constexpr auto operator==(const ModInt<MOD, T>& m) const {      return !(x != m.x);    }        constexpr friend std::ostream& operator<<(std::ostream& os,                                              const ModInt<MOD, T>& m) {      return os << m.x;    }    constexpr friend std::istream& operator>>(std::istream& is,                                              ModInt<MOD, T>& m) {      return is >> m.x;    }    constexpr auto val() const { return x; }  };}  

signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);
  constexpr long long MOD = 1e9 + 7;
  using mint = mtd::ModInt<MOD>;

  long long n;
  std::cin >> n;

  mtd::Matrix<mint> mat({{-1, 1}, {0, 3}});
  auto mat_p = mat.pow(n);
  mint ans = mat_p[0][0] + mat_p[0][1];
  std::cout << ans << std::endl;
}
0