結果
問題 | No.793 うし数列 2 |
ユーザー |
![]() |
提出日時 | 2019-02-22 21:46:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 7,099 bytes |
コンパイル時間 | 1,846 ms |
コンパイル使用メモリ | 179,952 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-25 06:59:56 |
合計ジャッジ時間 | 2,556 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define INF_LL (int64)1e18#define INF (int32)1e9#define REP(i, n) for(int64 i = 0;i < (n);i++)#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)#define all(x) x.begin(),x.end()#define fs first#define sc secondusing int32 = int_fast32_t;using uint32 = uint_fast32_t;using int64 = int_fast64_t;using uint64 = uint_fast64_t;using PII = pair<int32, int32>;using PLL = pair<int64, int64>;const double eps = 1e-10;template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}template<::std::uint_fast64_t mod>class ModInt{private:using value_type = ::std::uint_fast64_t;value_type n;public:ModInt() : n(0) {}ModInt(value_type n_) : n(n_ % mod) {}ModInt(const ModInt& m) : n(m.n) {}template<typename T>explicit operator T() const { return static_cast<T>(n); }value_type get() const { return n; }friend ::std::ostream& operator<<(::std::ostream &os, const ModInt<mod> &a) {return os << a.n;}friend ::std::istream& operator>>(::std::istream &is, ModInt<mod> &a) {value_type x;is >> x;a = ModInt<mod>(x);return is;}bool operator==(const ModInt& m) const { return n == m.n; }bool operator!=(const ModInt& m) const { return n != m.n; }ModInt& operator*=(const ModInt& m){ n = n * m.n % mod; return *this; }ModInt pow(value_type b) const{ModInt ans = 1, m = ModInt(*this);while(b){if(b & 1) ans *= m;m *= m;b >>= 1;}return ans;}ModInt inv() const { return (*this).pow(mod-2); }ModInt& operator+=(const ModInt& m){ n += m.n; n = (n < mod ? n : n - mod); return *this; }ModInt& operator-=(const ModInt& m){ n += mod - m.n; n = (n < mod ? n : n - mod); return *this; }ModInt& operator/=(const ModInt& m){ *this *= m.inv(); return *this; }ModInt operator+(const ModInt& m) const { return ModInt(*this) += m; }ModInt operator-(const ModInt& m) const { return ModInt(*this) -= m; }ModInt operator*(const ModInt& m) const { return ModInt(*this) *= m; }ModInt operator/(const ModInt& m) const { return ModInt(*this) /= m; }ModInt& operator++(){ n += 1; return *this; }ModInt& operator--(){ n -= 1; return *this; }ModInt operator++(int){ModInt old(n);n += 1;return old;}ModInt operator--(int){ModInt old(n);n -= 1;return old;}ModInt operator-() const { return ModInt(mod-n); }};template<typename T>class Matrix{private:using size_type = ::std::size_t;using Row = ::std::vector<T>;using Mat = ::std::vector<Row>;size_type R, C; // row, columnMat A;void add_row_to_another(size_type r1, size_type r2, const T k){ // Row(r1) += Row(r2)*kfor(size_type i = 0;i < C;i++)A[r1][i] += A[r2][i]*k;}void scalar_multiply(size_type r, const T k){for(size_type i = 0;i < C;i++)A[r][i] *= k;}void scalar_division(size_type r, const T k){for(size_type i = 0;i < C;i++)A[r][i] /= k;}public:Matrix(){}Matrix(size_type r, size_type c) : R(r), C(c), A(r, Row(c)) {}Matrix(const Mat &m) : R(m.size()), C(m[0].size()), A(m) {}Matrix(const Mat &&m) : R(m.size()), C(m[0].size()), A(m) {}Matrix(const Matrix<T> &m) : R(m.R), C(m.C), A(m.A) {}Matrix(const Matrix<T> &&m) : R(m.R), C(m.C), A(m.A) {}Matrix<T> &operator=(const Matrix<T> &m){R = m.R; C = m.C; A = m.A;return *this;}Matrix<T> &operator=(const Matrix<T> &&m){R = m.R; C = m.C; A = m.A;return *this;}static Matrix I(const size_type N){Matrix m(N, N);for(size_type i = 0;i < N;i++) m[i][i] = 1;return m;}const Row& operator[](size_type k) const& { return A.at(k); }Row& operator[](size_type k) & { return A.at(k); }Row operator[](size_type k) const&& { return ::std::move(A.at(k)); }size_type row() const { return R; } // the number of rowssize_type column() const { return C; }T determinant(){assert(R == C);Mat tmp = A;T res = 1;for(size_type i = 0;i < R;i++){for(size_type j = i;j < R;j++){ // satisfy A[i][i] > 0if (A[j][i] != 0) {if (i != j) res *= -1;swap(A[j], A[i]);break;}}if (A[i][i] == 0) return 0;res *= A[i][i];scalar_division(i, A[i][i]);for(size_type j = i+1;j < R;j++){add_row_to_another(j, i, -A[j][i]);}}swap(tmp, A);return res;}Matrix inverse(){assert(R == C);assert(determinant() != 0);Matrix inv(Matrix::I(R)), tmp(*this);for(size_type i = 0;i < R;i++){for(size_type j = i;j < R;j++){if (A[j][i] != 0) {swap(A[j], A[i]);swap(inv[j], inv[i]);break;}}inv.scalar_division(i, A[i][i]);scalar_division(i, A[i][i]);for(size_type j = 0;j < R;j++){if(i == j) continue;inv.add_row_to_another(j, i, -A[j][i]);add_row_to_another(j, i, -A[j][i]);}}(*this) = tmp;return inv;}Matrix& operator+=(const Matrix &B){assert(column() == B.column() && row() == B.row());for(size_type i = 0;i < R;i++)for(size_type j = 0;j < C;j++)(*this)[i][j] += B[i][j];return *this;}Matrix& operator-=(const Matrix &B){assert(column() == B.column() && row() == B.row());for(size_type i = 0;i < R;i++)for(size_type j = 0;j < C;j++)(*this)[i][j] -= B[i][j];return *this;}Matrix& operator*=(const Matrix &B){assert(column() == B.row());Matrix M(R, B.column());for(size_type i = 0;i < R;i++) {for(size_type j = 0;j < B.column();j++) {M[i][j] = 0;for(size_type k = 0;k < C;k++) {M[i][j] += (*this)[i][k] * B[k][j];}}}swap(M, *this);return *this;}Matrix& operator/=(const Matrix &B){assert(C == B.row());Matrix M(B);(*this) *= M.inverse();return *this;}Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); }Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); }Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); }Matrix operator/(const Matrix &B) const { return (Matrix(*this) /= B); }bool operator==(const Matrix &B) const {if (column() != B.column() || row() != B.row()) return false;for(size_type i = 0;i < row();i++)for(size_type j = 0;j < column();j++)if ((*this)[i][j] != B[i][j]) return false;return true;}bool operator!=(const Matrix &B) const { return !((*this) == B); }Matrix pow(size_type k){assert(R == C);Matrix M(Matrix::I(R));while(k){if (k & 1) M *= (*this);k >>= 1;(*this) *= (*this);}A.swap(M.A);return *this;}friend ::std::ostream &operator<<(::std::ostream &os, Matrix &p){for(size_type i = 0;i < p.row();i++){for(size_type j = 0;j < p.column();j++){os << p[i][j] << " ";}os << ::std::endl;}return os;}};const int64 mod = 1e9+7;using Mint = ModInt<mod>;using Mat = Matrix<ModInt<mod>>;int main(void){cin.tie(0);ios::sync_with_stdio(false);vector<vector<Mint>> aa = {{10, 3}, {0, 1}};vector<vector<Mint>> bb = {{1}, {1}};Mat a(aa), b(bb);int64 N;cin >> N;a.pow(N);Mat c = a * b;cout << c[0][0] << endl;}