結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0