結果
問題 | No.526 フィボナッチ数列の第N項をMで割った余りを求める |
ユーザー |
![]() |
提出日時 | 2022-06-23 19:54:01 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 7,886 bytes |
コンパイル時間 | 3,957 ms |
コンパイル使用メモリ | 237,168 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-07 12:57:11 |
合計ジャッジ時間 | 4,751 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 1 ms
5,248 KB |
testcase_14 | AC | 2 ms
5,248 KB |
ソースコード
#include "bits/stdc++.h" #include <numeric> #include <atcoder/all> using namespace std; using namespace atcoder; // clang-format off /* accelration */ // 高速バイナリ生成 #pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") // cin cout の結びつけ解除, stdioと同期しない(入出力非同期化) // cとstdの入出力を混在させるとバグるので注意 struct Fast { Fast() { std::cin.tie(0); ios::sync_with_stdio(false); } } fast; /* alias */ using ull = unsigned long long; using ll = long long; using vi = vector<int>; using vl = vector<long>; using vll = vector<long long>; using vvi = vector<vi>; using vvl = vector<vl>; using vvll = vector<vll>; using vs = vector<string>; using pii = pair<int, int>; using pll = pair<ll, ll>; using vb = vector<bool>; using vvb = vector<vb>; /* define short */ #define pb push_back // #define mp make_pair #define all(obj) (obj).begin(), (obj).end() #define YESNO(bool) if(bool){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;} #define yesno(bool) if(bool){cout<<"yes"<<endl;}else{cout<<"no"<<endl;} #define YesNo(bool) if(bool){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;} /* REP macro */ #define reps(i, a, n) for (ll i = (a); i < (ll)(n); ++i) #define rep(i, n) reps(i, 0, n) #define rrep(i, n) reps(i, 1, n + 1) #define repd(i,n) for(ll i=n-1;i>=0;i--) #define rrepd(i,n) for(ll i=n;i>=1;i--) #define repsd(i, n, a) for(ll i=n;i>=a;i--) #define fore(i,a) for(auto &i:a) /* debug */ // 標準エラー出力を含む提出はrejectされる場合もあるので注意 #define debug(x) cerr << "\033[33m(line:" << __LINE__ << ") " << #x << ": " << x << "\033[m" << endl; /* func */ inline int in_int() { int x; cin >> x; return x; } inline ll in_ll() { ll x; cin >> x; return x; } inline string in_str() { string x; cin >> x; return x; } // search_length: 走査するベクトル長の上限(先頭から何要素目までを検索対象とするか、1始まりで) template <typename T> inline bool vector_finder(std::vector<T> vec, T element, unsigned int search_length) { auto itr = std::find(vec.begin(), vec.end(), element); size_t index = std::distance(vec.begin(), itr); if (index == vec.size() || index >= search_length) { return false; } else { return true; } } template <typename T> inline void print(const vector<T>& v, string s = " ") { rep(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n"); } template <typename T, typename S> inline void print(const pair<T, S>& p) { cout << p.first << " " << p.second << endl; } template <typename T> inline void print(const T& x) { cout << x << "\n"; } inline void printd(double x) { cout << fixed << setprecision(8) << x << endl; } template <typename T, typename S> inline void print(const vector<pair<T, S>>& v) { for (auto&& p : v) print(p); } // 第一引数と第二引数を比較し、第一引数(a)をより大きい/小さい値に上書き template <typename T> inline bool chmin(T& a, const T& b) { bool compare = a > b; if (a > b) a = b; return compare; } template <typename T> inline bool chmax(T& a, const T& b) { bool compare = a < b; if (a < b) a = b; return compare; } // gcd lcm // C++17からは標準実装 // template <typename T> T gcd(T a, T b) {if (b == 0)return a; else return gcd(b, a % b);} // template <typename T> inline T lcm(T a, T b) {return (a * b) / gcd(a, b);} // clang-format on // グラフテンプレート template< typename T > struct edge { int src, to; T cost; edge(int to, T cost) : src(-1), to(to), cost(cost) {} edge(int src, int to, T cost) : src(src), to(to), cost(cost) {} edge& operator=(const int& x) { to = x; return *this; } operator int() const { return to; } }; template< typename T > using Edges = vector< edge< T > >; template< typename T > using WeightedGraph = vector< Edges< T > >; using UnWeightedGraph = vector< vector< int > >; template< class T > struct Matrix { vector< vector< T > > A; Matrix() {} Matrix(size_t n, size_t m) : A(n, vector< T >(m, 0)) {} Matrix(size_t n) : A(n, vector< T >(n, 0)) {}; size_t height() const { return (A.size()); } size_t width() const { return (A[0].size()); } inline const vector< T >& operator[](int k) const { return (A.at(k)); } inline vector< T >& operator[](int k) { return (A.at(k)); } static Matrix I(size_t n) { Matrix mat(n); for (int i = 0; i < n; i++) mat[i][i] = 1; return (mat); } Matrix& operator+=(const Matrix& B) { size_t n = height(), m = width(); assert(n == B.height() && m == B.width()); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) (*this)[i][j] += B[i][j]; return (*this); } Matrix& operator-=(const Matrix& B) { size_t n = height(), m = width(); assert(n == B.height() && m == B.width()); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) (*this)[i][j] -= B[i][j]; return (*this); } Matrix& operator*=(const Matrix& B) { size_t n = height(), m = B.width(), p = width(); assert(p == B.height()); vector< vector< T > > C(n, vector< T >(m, 0)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int k = 0; k < p; k++) C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]); A.swap(C); return (*this); } Matrix& operator^=(long long k) { Matrix B = Matrix::I(height()); while (k > 0) { if (k & 1) B *= *this; *this *= *this; k >>= 1LL; } A.swap(B.A); 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 long long k) const { return (Matrix(*this) ^= k); } friend ostream& operator<<(ostream& os, Matrix& p) { size_t n = p.height(), m = p.width(); for (int i = 0; i < n; i++) { os << "["; for (int j = 0; j < m; j++) { os << p[i][j] << (j + 1 == m ? "]\n" : ","); } } return (os); } T determinant() { Matrix B(*this); assert(width() == height()); T ret = 1; for (int i = 0; i < width(); i++) { int idx = -1; for (int j = i; j < width(); j++) { if (B[j][i] != 0) idx = j; } if (idx == -1) return (0); if (i != idx) { ret *= -1; swap(B[i], B[idx]); } ret *= B[i][i]; T vv = B[i][i]; for (int j = 0; j < width(); j++) { B[i][j] /= vv; } for (int j = i + 1; j < width(); j++) { T a = B[j][i]; for (int k = 0; k < width(); k++) { B[j][k] -= B[i][k] * a; } } } return (ret); } }; // 定数 const ll INF = 1ll << 60, invINF = -(1ll << 60); const vi dd({ -1,0,1,0,-1 }); const ll MOD = 1000000007; const double PI = acos(-1); // 最大公約数 ll gcd(ll a, ll b) { if (!b) return a; if (a % b == 0) return b; else return gcd(b, a % b); } // 最小公倍数 ll lcm(ll a, ll b) { return a * b / gcd(a, b); } //using mint = modint1000000007; int main() { int n, m; cin >> n >> m; modint::set_mod(m); Matrix<modint> A(2, 2); A[0][0] = 1; A[0][1] = 1; A[1][0] = 1; A ^= n-1; print(A[1][0].val()); }