結果

問題 No.2156 ぞい文字列
コンテスト
ユーザー Suu0313
提出日時 2022-12-09 21:33:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 7,178 bytes
コンパイル時間 2,345 ms
コンパイル使用メモリ 204,700 KB
最終ジャッジ日時 2025-02-09 07:29:17
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template< int mod >
struct ModInt {
  int x;

  constexpr ModInt() : x(0) {}

  constexpr ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
  
  constexpr ModInt &operator+=(const ModInt &p) {
    if((x += p.x) >= mod) x -= mod;
    return *this;
  }
  constexpr ModInt &operator-=(const ModInt &p) {
    if((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  constexpr ModInt &operator*=(const ModInt &p) {
    x = (int) (1LL * x * p.x % mod);
    return *this;
  }
  constexpr ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }
  constexpr ModInt operator-() const { return ModInt(-x); }
  constexpr ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
  constexpr ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
  constexpr ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
  constexpr ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
  constexpr bool operator==(const ModInt &p) const { return x == p.x; }
  constexpr bool operator!=(const ModInt &p) const { return x != p.x; }
  constexpr bool operator<(const ModInt &p) const { return x < p.x; }

  constexpr ModInt& operator++() { (*this).x+=1; return (*this); }
  constexpr ModInt& operator--() { (*this).x-=1; return (*this); }
  constexpr ModInt operator++(int) { ModInt tmp(*this); ++(*this); return tmp; }
  constexpr ModInt operator--(int) { ModInt tmp(*this); --(*this); return tmp; }

  constexpr ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }
  constexpr ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while(n > 0) {
      if(n & 1) ret *= mul;
      mul *= mul; n >>= 1;
    }
    return ret;
  }
  friend ostream &operator<<(ostream &os, const ModInt &p) {
    return os << p.x;
  }
  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt< mod >(t);
    return (is);
  }
  constexpr static int get_mod() { return mod; }
};
template< int mod >
constexpr ModInt<mod> operator+(const int64_t &p, const ModInt<mod> &m){ return ModInt<mod>(p) + m; };
template< int mod >
constexpr ModInt<mod> operator-(const int64_t &p, const ModInt<mod> &m){ return ModInt<mod>(p) - m; };
template< int mod >
constexpr ModInt<mod> operator*(const int64_t &p, const ModInt<mod> &m){ return ModInt<mod>(p) * m; };
template< int mod >
constexpr ModInt<mod> operator/(const int64_t &p, const ModInt<mod> &m){ return ModInt<mod>(p) / m; };

//constexpr int MOD = 1e9 + 7;
constexpr int MOD = 998244353;
using mint = ModInt< MOD >;
using VM = vector<mint>;
using VVM = vector<VM>;

namespace mintliteral{ constexpr mint operator""_m(unsigned long long x) { return mint(x); } }
using namespace mintliteral;

template<typename T>
struct Matrix{
  vector<vector<T>> a;
  Matrix() = default;
  Matrix(size_t n): Matrix(n, n) {}
  Matrix(size_t n, size_t m, const T &e = T()): a(n, vector<T>(m, e)) {}
  Matrix(const vector<vector<T>> &a): a(a) {}

  Matrix(const Matrix&) = default;
  Matrix(Matrix&&) = default;
  Matrix &operator=(const Matrix&) = default;
  Matrix &operator=(Matrix&&) = default;

  size_t height() const { return a.size(); }
  size_t width() const { return a[0].size(); }

  vector<T> &operator[](size_t k) { return a[k]; }
  const vector<T> &operator[](size_t k) const { return a[k]; }

  static Matrix I(size_t n){
    Matrix res(n);
    for (size_t i = 0; i < n; i++) res[i][i] = 1;
    return res;
  }

  Matrix Transpose() const {
    size_t n = height(), m = width();
    Matrix res(m, n);
    for (size_t i = 0; i < n; i++)
      for (size_t j = 0; j < m; j++)
        res[j][i] = a[i][j];
    return res;
  }

  Matrix &operator+=(const Matrix &b){
    assert(height() == b.height() && width() == b.width());
    size_t n = height(), m = width();
    for (size_t i = 0; i < n; i++)
      for (size_t j = 0; j < m; j++)
        (*this)[i][j] += b[i][j];
    return (*this);
  }
  
  Matrix &operator-=(const Matrix &b){
    assert(height() == b.height() && width() == b.width());
    size_t n = height(), m = width();
    for (size_t i = 0; i < n; i++)
      for (size_t j = 0; j < m; j++)
        (*this)[i][j] -= b[i][j];
    return (*this);
  }

  Matrix &operator*=(const T &c){
    size_t n = height(), m = width();
    for (size_t i = 0; i < n; i++)
      for (size_t j = 0; j < m; j++)
        (*this)[i][j] *= c;
    return (*this);
  }

  Matrix &operator*=(const Matrix &b){
    assert(width() == b.height());
    size_t n = height(), m = b.width(), l = width();
    vector<vector<T>> c(n, vector<T>(m));
    for (size_t i = 0; i < n; i++)
      for (size_t k = 0; k < l; k++)
        for (size_t j = 0; j < m; j++)
          c[i][j] += (*this)[i][k] * b[k][j];
    a.swap(c);
    return (*this);
  }

  Matrix &operator/=(const T &c){
    return (*this) *= T(1)/c;
  }

  Matrix &operator^=(int64_t k){
    assert(height() == width());
    Matrix m = Matrix::I(height());
    while(k > 0){
      if(k&1) m *= (*this);
      (*this) *= (*this); k >>= 1;
    }
    a.swap(m.a);
    return (*this);
  }

  Matrix operator-() const {
    Matrix m(*this);
    for(auto&&v : m.a) for(auto&&e : v) e = -e;
    return m;
  }

  Matrix operator+(const Matrix &b) const { return Matrix(*this) += b; }
  Matrix operator-(const Matrix &b) const { return Matrix(*this) -= b; }
  Matrix operator*(const T &c) const { return Matrix(*this) *= c; }
  Matrix operator*(const Matrix &b) const { return Matrix(*this) *= b; }
  Matrix operator/(const T &c) const { return Matrix(*this) /= c; }
  Matrix operator^(int64_t k) const { return Matrix(*this) ^= k; }

  Matrix pow(int64_t k) const { return (*this) ^ k; }

  vector<T> operator*(const vector<T> &x) const {
    assert(width() == x.size());
    size_t n = height(), m = width();
    vector<T> res(n);
    for (size_t i = 0; i < n; i++)
      for (size_t j = 0; j < m; j++)
        res[i] += (*this)[i][j] * x[j];
    return res;
  }

  T sum() const {
    T res = 0;
    for(const auto& v : a) res += accumulate(begin(v), end(v), T(0));
    return res;
  }

  T tr() const {
    T res = 0;
    for(size_t i = 0, n = height(); i < n; ++i) res += (*this)[i][i];
    return res;
  }

  #define def_cmp(cmp) bool operator cmp (const Matrix &b) const { return a cmp b.a; }
  def_cmp(==)
  def_cmp(!=)
  def_cmp(<)
  def_cmp(>)
  def_cmp(<=)
  def_cmp(>=)
  #undef def_cmp
  

  friend istream &operator>>(istream &is, Matrix &p){
    size_t n = p.height(), m = p.width();
    for (size_t i = 0; i < n; i++)
      for (size_t j = 0; j < m; j++)
        is >> p[i][j];
    return (is);
  }

  friend ostream &operator<<(ostream &os, const Matrix &p){
    size_t n = p.height(), m = p.width();
    for (size_t i = 0; i < n; i++)
      for (size_t j = 0; j < m; j++)
        os << p[i][j] << " \n"[j+1==m];
    return (os);
  }
};


int main() {
  int64_t n; cin >> n;
  Matrix<mint> m({{1, 1}, {1, 0}});
  auto re = (m ^ (n-1)) * VM({1, 0});

  cout << re[0] + re[1] - 1 << "\n";
}
0