結果
問題 | No.314 ケンケンパ |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;}