結果
問題 | No.718 行列のできるフィボナッチ数列道場 (1) |
ユーザー | |
提出日時 | 2019-11-10 13:43:53 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 7,837 bytes |
コンパイル時間 | 1,397 ms |
コンパイル使用メモリ | 110,820 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 04:57:42 |
合計ジャッジ時間 | 2,253 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
ソースコード
// #define NDEBUG #include <unordered_map> #include <functional> #include <algorithm> #include <iostream> #include <cassert> #include <cstring> #include <iomanip> #include <string> #include <vector> #include <queue> #include <tuple> #include <set> #include <map> // [0, max) #define FOR0(var, max) for (sl (var) = 0; (var) < (max); ++(var)) // [min, max) #define FORi(var, min, max) for (sl (var) = (min); (var) < (max); ++(var)) // [min, max) #define FORi_INV(var, min, max) for (sl (var) = (max) - 1; (var) + 1 > (min); --(var)) #define FORITER(var, iter) for (auto (iter) = (var).begin(); (iter) != (var).end(); (iter)++) #define FORITER_INV(var, iter) for (auto (iter) = (var).rbegin(); (iter) != (var).rend(); (iter)++) // a < b < c #define LTLT(a, b, c) (((a) < (b)) && ((b) < (c))) // a <= b < c #define LELT(a, b, c) (((a) <= (b)) && ((b) < (c))) // a < b <= c #define LTLE(a, b, c) (((a) < (b)) && ((b) <= (c))) // a <= b <= c #define LELE(a, b, c) (((a) <= (b)) && ((b) <= (c))) #ifndef NDEBUG # define MASSERT(cond) m_assert(cond, __LINE__, #cond); #else # define MASSERT(...) #endif using namespace std; using uc = unsigned char; using ui = unsigned int; using ul = unsigned long long int; using sc = signed char; using si = signed int; using sl = signed long long int; using ld = long double; void m_assert(const bool& cond, const sl& line, const char *condstr) { if (!cond) { cerr << "Assertion Failed: " << condstr << " at line " << line << endl; exit(1); } } template <class T> tuple<T, T, T> xgcd(const T& a0, const T& b0) { T a = a0, b = b0; T x = 0, y = 1, u = 1, v = 0; while (a != 0) { auto q = b / a; auto r = b % a; auto m = x - u * q; auto n = y - v * q; b = a; a = r; x = u; y = v; u = m; v = n; } return make_tuple(b, x, y); } sl modinv(const sl& a, const sl& m) { auto t = xgcd(a, m); MASSERT(std::get<0>(t) == 1); auto res = std::get<1>(t) % m; if (res < 0) { res += m; } res %= m; return res; } template <class T> struct Matrix { sl N, M; vector<vector<T>> mat; static Matrix<T> Identity(const sl& N) { Matrix<T> ret(N, N); FOR0(i, N) { ret.mat[i][i] = 1; } return std::move(ret); } static Matrix<T> Zero(const sl& N, const sl& M) { Matrix<T> ret(N, M); return std::move(ret); } Matrix(const sl& _N, const sl& _M) : N(_N), M(_M) { MASSERT(0 < N); MASSERT(0 < M); mat.resize(N); FOR0(i, N) { mat[i].resize(M, 0); } } Matrix(const Matrix<T>& _from) : N(_from.N), M(_from.M), mat(_from.mat) {} Matrix<T> operator=(const Matrix<T>& _from) { N = _from.N; M = _from.M; mat = _from.mat; return *this; } inline Matrix<T> add(const Matrix<T>& B) const { MASSERT(N == B.N); MASSERT(M == B.M); Matrix<T> ret(*this); FOR0(i, N) { FOR0(j, M) { ret.mat[i][j] += B.mat[i][j]; } } return std::move(ret); } inline Matrix<T> sub(const Matrix<T>& B) const { MASSERT(N == B.N); MASSERT(M == B.M); Matrix<T> ret(*this); FOR0(i, N) { FOR0(j, M) { ret.mat[i][j] -= B.mat[i][j]; } } return std::move(ret); } inline Matrix<T> mult(const Matrix<T>& B) const { MASSERT(M == B.N); Matrix<T> ret(N, B.M); FOR0(i, N) { FOR0(k, M) { auto mik = mat[i][k]; FOR0(j, B.M) { ret[i][j] += (mik * B[k][j]); } } } return std::move(ret); } inline Matrix<T> power(const sl& x) const { MASSERT(0 < x); MASSERT(N == M); Matrix<T> ret = Matrix<T>::Identity(N); Matrix<T> temp = *this; sl t = x; while (t != 0) { if ((t & 1) == 1) { ret = ret.mult(temp); } temp = temp.mult(temp); t >>= 1; } return std::move(ret); } inline Matrix<T> scalarmult(const T& s) const { Matrix<T> ret(*this); FOR0(i, N) { FOR0(j, M) { ret.mat[i][j] *= s; } } return std::move(ret); } const vector<T>& operator[](const sl& idx) const { MASSERT(LELT(0, idx, N)); return mat[idx]; } vector<T>& operator[](const sl& idx) { MASSERT(LELT(0, idx, N)); return mat[idx]; } inline T determinant(void) const { MASSERT(N == M); vector<vector<T>> m = mat; T ret = 1; FOR0(i, N) { if (m[i][i] == 0) { FOR0(j, N) { if (m[j][i] != 0) { swap(m[i], m[j]); ret = -ret; break; } } } } FOR0(i, N) { FORi(j, i + 1, N) { auto c = -m[j][i] / m[i][i]; FORi(k, i + 1, M) { m[j][k] += c * m[i][k]; } } ret *= m[i][i]; } return std::move(ret); } }; template <sl Mod> struct Z_over_nZ{ sl x; Z_over_nZ(const sl& _x) : x(_x % Mod) { if (x < 0) { x += Mod; } } template <class T> Z_over_nZ<Mod> operator+=(const T& y) { x += y; x %= Mod; return *this; } template <class T> Z_over_nZ<Mod> operator-=(const T& y) { x -= y; x %= Mod; return *this; } template <class T> Z_over_nZ<Mod> operator*=(const T& y) { x *= y; x %= Mod; return *this; } template <class T> Z_over_nZ<Mod> operator/=(const T& y) { x *= modinv(y, Mod); x %= Mod; return *this; } Z_over_nZ<Mod> operator+=(const Z_over_nZ<Mod>& y) { return (*this) += y.x; } Z_over_nZ<Mod> operator-=(const Z_over_nZ<Mod>& y) { return (*this) -= y.x; } Z_over_nZ<Mod> operator*=(const Z_over_nZ<Mod>& y) { return (*this) *= y.x; } Z_over_nZ<Mod> operator/=(const Z_over_nZ<Mod>& y) { return (*this) /= y.x; } template <class T> Z_over_nZ<Mod> operator+(const T& y) const { return Z_over_nZ(*this) += y; } template <class T> Z_over_nZ<Mod> operator-(const T& y) const { return Z_over_nZ(*this) -= y; } template <class T> Z_over_nZ<Mod> operator*(const T& y) const { return Z_over_nZ(*this) *= y; } template <class T> Z_over_nZ<Mod> operator/(const T& y) const { return Z_over_nZ(*this) /= y; } Z_over_nZ<Mod> operator-() const { return Z_over_nZ(Mod - x); } template <class T> bool operator!=(const T& y) const { return !(*this == y); } template <class T> bool operator==(const T& y) const { return (x - y) % Mod == 0; } bool operator==(const Z_over_nZ<Mod>& y) const { return (x - y.x) % Mod == 0; } template <class T> Z_over_nZ<Mod> operator=(const T& y) { x = y; return *this; } Z_over_nZ<Mod> operator=(const Z_over_nZ& y) { x = y.x; return *this; } }; template <sl Mod> ostream& operator<<(ostream& os, const Z_over_nZ<Mod>& x) { os << x.x; return os; } template <class T> ostream& operator<<(ostream& os, const Matrix<T>& mat) { os << "["; FOR0(i, mat.N) { os << "["; FOR0(j, mat.M) { os << mat.mat[i][j]; if (j != mat.M - 1) { os << ", "; } } os << "]"; if (i != mat.N - 1) { os << ", "; } } os << "]"; return os; } template <class T> T powmod(T x, ul y, ul z) { T cur = x; T res = 1; while (y != 0) { if ((y & 1) == 1) { res = (res * cur) % z; } cur = (cur * cur) % z; y >>= 1; } return res; } static sl N, M; using Zmod1000000007 = Z_over_nZ<1000000007>; void solve(void) { Matrix<Zmod1000000007> mat(4, 4); Matrix<Zmod1000000007> yvec(4, 1); mat[0][0] = 1; mat[0][1] = 1; mat[0][2] = 2; mat[1][0] = 1; mat[2][0] = 1; mat[2][2] = 1; mat[3][0] = 1; mat[3][1] = 1; mat[3][2] = 2; mat[3][3] = 1; yvec[0][0] = 1; yvec[1][0] = 1; yvec[2][0] = 1; yvec[3][0] = 2; auto mat2 = mat.power(N - 2).mult(yvec); cout << mat2[3][0] << endl; } int main(void) { cin >> N >> M; solve(); return 0; }