結果

問題 No.314 ケンケンパ
ユーザー not_522
提出日時 2016-11-23 12:43:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 37 ms / 1,000 ms
コード長 7,679 bytes
コンパイル時間 2,130 ms
コンパイル使用メモリ 182,616 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-11-27 10:19:16
合計ジャッジ時間 3,154 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

template<typename T> class Addition {
public:
  template<typename V> T operator+(const V& v) const {
    return T(static_cast<const T&>(*this)) += v;
  }
};

template<typename T> class Subtraction {
public:
  template<typename V> T operator-(const V& v) const {
    return T(static_cast<const T&>(*this)) -= v;
  }
};

template<typename T> class Multiplication {
public:
  template<typename V> T operator*(const V& v) const {
    return T(static_cast<const T&>(*this)) *= v;
  }
};

template<typename T> class Division {
public:
  template<typename V> T operator/(const V& v) const {
    return T(static_cast<const T&>(*this)) /= v;
  }
};

template<typename T> class Modulus {
public:
  template<typename V> T operator%(const V& v) const {
    return T(static_cast<const T&>(*this)) %= v;
  }
};

template<typename T> class IndivisibleArithmetic : public Addition<T>, public Subtraction<T>, public Multiplication<T> {};

template<typename T> class Arithmetic : public IndivisibleArithmetic<T>, public Division<T> {};

class Inverse {
private:
  long long mod;
  vector<long long> inv;
  
public:
  Inverse() {}
  
  Inverse(long long mod, long long n = 1000000) : mod(mod), inv(n, 1) {for (int i = 2; i < n; ++i) inv[i] = inv[mod % i] * (mod - mod / i) % mod;}
  
  long long operator()(long long a) const {
    if (a < (int)inv.size()) return inv[a];
    long long b = mod, x = 1, y = 0;
    while (b) {
      long long t = a / b;
      swap(a -= t * b, b);
      swap(x -= t * y, y);
    }
    return (x %= mod) < 0 ? x + mod : x;
  }
};

class Mint : public Arithmetic<Mint> {
private:
  static long long mod;
  static Inverse inverse;
  long long val;

public:
  Mint() : val(0) {}

  Mint(const long long& val) {
    this->val = val % mod;
    if (this->val < 0) this->val += mod;
  }

  static void setMod(const long long& m) {
    mod = m;
    inverse = Inverse(m);
  }

  Mint operator+=(const Mint& m) {
    val += m.val;
    if (val >= mod) val -= mod;
    return *this;
  }

  Mint operator-=(const Mint& m) {
    val -= m.val;
    if (val < 0) val += mod;
    return *this;
  }

  Mint operator*=(const Mint& m) {
    val *= m.val;
    val %= mod;
    return *this;
  }

  Mint operator/=(const Mint& m) {
    val *= inverse(m.val);
    val %= mod;
    return *this;
  }

  Mint operator++() {return *this += 1;}

  Mint operator--() {return *this -= 1;}

  operator long long() {return val;}

  Mint identity() const {return 1;}
};

long long Mint::mod = 1000000007;
Inverse Mint::inverse(1000000007);

ostream& operator<<(ostream& os, Mint a) {
  os << (long long)a;
  return os;
}

istream& operator>>(istream& is, Mint& a) {
  long long n;
  is >> n;
  a = n;
  return is;
}

template<typename T> T pow(const T& m, long long n) {
  if (n == 0) {
    return m.identity();
  } else if (n < 0) {
    return m.identity() / pow(m, -n);
  }
  T mm = pow(m, n / 2);
  mm *= mm;
  if (n % 2) mm *= m;
  return mm;
}

template<typename T> class Ordered {
public:
  template<typename V> bool operator==(const V& v) const {
    return !(static_cast<T>(v) < static_cast<const T&>(*this) || static_cast<const T&>(*this) < static_cast<T>(v));
  }
  
  template<typename V> bool operator!=(const V& v) const {
    return static_cast<T>(v) < static_cast<const T&>(*this) || static_cast<const T&>(*this) < static_cast<T>(v);
  }

  template<typename V> bool operator>(const V& v) const {
    return static_cast<T>(v) < static_cast<const T&>(*this);
  }

  template<typename V> bool operator<=(const V& v) const {
    return !(static_cast<T>(v) < static_cast<const T&>(*this));
  }

  template<typename V> bool operator>=(const V& v) const {
    return !(static_cast<const T&>(*this) < static_cast<T>(v));
  }
};

template<typename T> class Vector : public Addition<Vector<T>>, public Subtraction<Vector<T>>, public Ordered<Vector<T>> {
protected:
  vector<T> val;

public:
  Vector(int n) : val(n, 0) {}

  T& operator[](int n) {
    return val[n];
  }

  Vector operator+=(const Vector& v) {
    for (int i = 0; i < size(); ++i) val[i] += v[i];
    return *this;
  }

  Vector operator-=(const Vector& v) {
    for (int i = 0; i < size(); ++i) val[i] -= v[i];
    return *this;
  }

  T operator*(const Vector& v) const {
    return inner_product(val.begin(), val.end(), const_cast<Vector&>(v).begin(), T(0));
  }

  bool operator<(const Vector& v) const {
    if (size() != v.size()) return size() < v.size();
    for (int i = 0; i < size(); ++i) if (val[i] != v.val[i]) return val[i] < v.val[i];
    return false;
  }

  int size() const {
    return val.size();
  }

  typename vector<T>::const_iterator begin() const {
    return val.begin();
  }

  typename vector<T>::const_iterator end() const {
    return val.end();
  }
};

template<typename T> class Matrix : public Addition<Matrix<T>>, public Subtraction<Matrix<T>>, public Ordered<Matrix<T>> {
protected:
  vector<Vector<T>> val;

public:
  Matrix(int n, int m) : val(n, Vector<T>(m)) {}

  Vector<T>& operator[](int n) {return val[n];}

  Matrix operator+=(const Matrix& m) {
    for (int i = 0; i < (int)val.size(); ++i) val[i] += m[i];
    return *this;
  }

  Matrix operator-=(const Matrix& m) {
    for (int i = 0; i < (int)val.size(); ++i) val[i] -= m[i];
    return *this;
  }

  Matrix operator*=(const Matrix& _m) {
    Matrix &m = const_cast<Matrix&>(_m);
    Matrix res(size(), m[0].size());
    for (int i = 0; i < size(); ++i) {
      for (int j = 0; j < m.size(); ++j) {
        for (int k = 0; k < m[0].size(); ++k) {
          res[i][k] += val[i][j] * m[j][k]; 
        }
      }
    }
    return *this = res;
  }

  Matrix operator*(const Matrix& m) const {
    Matrix res = *this;
    return res *= m;
  }

  Vector<T> operator*(const Vector<T>& v) {
    Vector<T> res(size());
    for (int i = 0; i < size(); ++i) res[i] += val[i] * v;
    return res;
  }

  bool operator<(const Matrix& m) const {
    if (size() != m.size()) return size() < m.size();
    for (int i = 0; i < size(); ++i) if (val[i] != m.val[i]) return val[i] < m.val[i];
    return false;
  }

  int size() const {
    return val.size();
  }
};

template<typename T> class SquareMatrix : public Matrix<T>, public Division<SquareMatrix<T>> {
public:
  SquareMatrix(int n) : Matrix<T>(n, n) {}

  SquareMatrix(const Matrix<T>& m) : Matrix<T>(m) {}

  SquareMatrix operator/=(const SquareMatrix& m) {
    return *this *= m.inverse();
  }

  SquareMatrix identity() const {
    SquareMatrix res(this->size());
    for (int i = 0; i < this->size(); ++i) res[i][i] = 1;
    return res;
  }

  SquareMatrix inverse() const {
    int n = this->size();
    SquareMatrix mat = *this;
    SquareMatrix inv = identity();
    for (int i = 0; i < n; ++i) {
      int p = i;
      for (int j = i + 1; j < n; ++j) {
        if (abs(mat[j][i]) > abs(mat[p][i])) p = j;
      }
      swap(mat[i], mat[p]);
      swap(inv[i], inv[p]);
      for (int j = i + 1; j < n; ++j) mat[i][j] /= mat[i][i];
      for (int j = 0; j < n; ++j) inv[i][j] /= mat[i][i];
      mat[i][i] = 1;
      for (int j = 0; j < n; ++j) {
        if (i == j) continue;
        T a = mat[j][i];
        for (int k = 0; k < n; ++k) {
          mat[j][k] -= a * mat[i][k];
          inv[j][k] -= a * inv[i][k];
        }
      }
    }
    return inv;
  }
};

int main() {
  int n;
  cin >> n;
  SquareMatrix<Mint> mat(3);
  mat[0][1] = 1;
  mat[0][2] = 1;
  mat[1][0] = 1;
  mat[2][1] = 1;
  mat = pow(mat, n - 1);
  cout << accumulate(mat[0].begin(), mat[0].end(), Mint()) << endl;
}
0