結果
問題 |
No.3228 Very Large Fibonacci Sum
|
ユーザー |
|
提出日時 | 2025-08-08 23:45:07 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 8,295 bytes |
コンパイル時間 | 1,728 ms |
コンパイル使用メモリ | 162,068 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2025-08-08 23:45:10 |
合計ジャッジ時間 | 3,123 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
// #define MOD_IS_998 1 #include <array> #if __has_include("template.hpp") && false #include "template.hpp" #else // template start #include <algorithm> #include <concepts> #include <cstdint> #include <iostream> #include <istream> #include <limits> #include <ostream> #include <queue> #include <random> #include <ranges> #include <set> #include <stdexcept> #include <string> #include <type_traits> #include <utility> #include <vector> #include <atcoder/modint.hpp> // often use #include <cassert> #include <ios> #include <map> using namespace std; using ll = long long; using pall = pair<ll, ll>; template<class T> using vec = vector<T>; template<class T> using veve = vec<vec<T>>; using vell = vec<ll>; using vest = vec<string>; using vebo = basic_string<bool>; using vevell = veve<ll>; template<class T> using mset = multiset<T>; template<class T> using priority_queue_ascend = priority_queue<T, vec<T>, greater<T>>; const ll inf = numeric_limits<ll>::max(); const string sp = " "; const string lf = "\n"; const auto &npos = string::npos; #ifdef MOD_IS_998 constexpr ll MOD = 998244353; #else constexpr ll MOD = 1e9 + 7; #endif const vec<pall> grid_move4 = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}}; const vec<pall> grid_move8 = [] { auto ret = grid_move4; ret.insert(ret.end(), {{-1, 1}, {-1, -1}, {1, -1}, {1, 1}}); return ret; }(); #define cont continue #define br break #define whlie while #define foR for #define auot auto #define uato auto #define cosnt const #define conts const #define ocnst const auto &ciN = cin; auto &icn = cin; auto &icN = cin; constexpr bool ture = true; constexpr bool flase = false; using namespace atcoder; using mint = static_modint<MOD>; #define times(N) \ static_assert(is_integral_v<decltype((N) + 0)>, \ "times(): N must be integral"); \ for(typedef decltype((N) + 0) _int; \ [[maybe_unused]] const _int _i : views::iota((_int)0, (N))) #define tiems times #define itmes times template<int M> decltype(auto) operator<<(ostream &out, const static_modint<M> &i) { return out << i.val(); } struct debug_stream { template<class T> debug_stream &operator<<([[maybe_unused]] const T &x) { #ifndef ONLINE_JUDGE clog << x; #endif return *this; } debug_stream &operator<<([[maybe_unused]] ostream &(*f)(ostream &)) { #ifndef ONLINE_JUDGE clog << f; #endif return *this; } }; template<class T> concept out_stream = same_as<ostream, T> || same_as<debug_stream, T>; debug_stream clog_; #define clog clog_ template<int M> istream &operator>>(istream &in, static_modint<M> &i) { intmax_t tmp; in >> tmp; tmp = (tmp % M + M) % M; i = tmp; return in; } template<class T, class U> istream &operator>>(istream &in, pair<T, U> &p) { return in >> p.first >> p.second; } template<class T, class U> decltype(auto) operator<<(out_stream auto &out, const pair<T, U> &p) { return out << p.first << sp << p.second; } template<class T> istream &operator>>(istream &in, vec<T> &v) { for(auto &&e : v) { in >> e; } return in; } namespace myinput { template<class... Ts> istream &in(Ts &...vecs) { static_assert(sizeof...(vecs) != 0, "myfunc::in(): At least one vector must be provided"); const set sizes = {vecs.size()...}; if(sizes.size() > 1) { throw invalid_argument("myfunc::in(): All vectors must have the same size"); } times(*sizes.begin()) { ((cin >> vecs[_i]), ...); } return cin; } } // namespace myinput using myinput::in; void out(ranges::range auto v, const string delim, out_stream auto &out) { for(auto &&e : v) { out << e << delim; } } void out(ranges::range auto v, const string delim) { out(v, delim, cout); } [[nodiscard]] const string &yesno(const bool cond, const string &yes = "Yes", const string &no = "No") noexcept { if(cond) return yes; return no; } // [mi, ma) [[nodiscard]] uint64_t randint(const uint64_t mi, const uint64_t ma) noexcept { static random_device seed; static mt19937_64 mt(seed()); if(mi > ma) [[unlikely]] return randint(ma, mi); if(mi == ma) [[unlikely]] return mi; const uint64_t w = ma - mi; uint64_t r; do { r = mt(); } while(mt.max() - mt.max() % w <= r); return r % w + mi; } template<class T, class U> requires common_with<T, U> [[nodiscard]] constexpr auto min(T &&a, U &&b) noexcept { return std::min<common_type_t<T, U>>(std::forward<T>(a), std::forward<U>(b)); } template<class T, class U> requires common_with<T, U> [[nodiscard]] constexpr auto max(T &&a, U &&b) noexcept { return std::max<common_type_t<T, U>>(std::forward<T>(a), std::forward<U>(b)); } template<class T> [[nodiscard]] const T &min(const vec<T> &v) { return *ranges::min_element(v); } template<class T> [[nodiscard]] const T &max(const vec<T> &v) { return *ranges::max_element(v); } template<class... Args> [[nodiscard]] auto reduce(const ranges::range auto &v, Args... args) { return reduce(v.begin(), v.end(), args...); } [[nodiscard]] constexpr ll powll(ll a, ll b, const ll m = inf) { if(b < 0) [[unlikely]] throw invalid_argument("powll(): exponent less than zero"); if(m < 1) [[unlikely]] throw invalid_argument("powll(): modulo less than one"); a %= m; ll ret = 1; while(b) { if(b % 2) ret *= a, ret %= m; a *= a, a %= m; b /= 2; } return ret; } template<class T, class U> requires assignable_from<T &, U> && totally_ordered_with<T, U> bool mini(T &var, U &&val) noexcept { const bool cmp = var > val; if(cmp) var = val; return cmp; } template<class T, class U> requires assignable_from<T &, U> && totally_ordered_with<T, U> bool maxi(T &var, U &&val) noexcept { const bool cmp = var < val; if(cmp) var = val; return cmp; } namespace myclass { class [[nodiscard]] grid_base { public: grid_base(const ll h, const ll w) noexcept : height(h), width(w) {} [[nodiscard]] ll operator()(const ll i, const ll j) const noexcept { if(! isvalid(i, j)) return -1; return i * width + j; } [[nodiscard]] ll operator()(const pall &p) const noexcept { return (*this)(p.first, p.second); } protected: bool isvalid(const ll i, const ll j) const noexcept { return 0 <= i && 0 <= j && i < height && j < width; } const ll height, width; }; class [[nodiscard]] grid_seen : public myclass::grid_base { public: grid_seen(const ll h, const ll w) : grid_base(h, w) { visited = vebo(h * w, false); } [[nodiscard]] bool &seen(const ll i, const ll j) & { if(! isvalid(i, j)) [[unlikely]] throw out_of_range("grid::seen(): out of range"); return visited[i * width + j]; } [[nodiscard]] bool &seen(const pall &p) & { return seen(p.first, p.second); } private: vebo visited; }; } // namespace myclass using grid_lite = myclass::grid_base; using myclass::grid_seen; template<class T> auto erase_single(mset<T> &mset, T &&v) { const auto it = mset.find(v); if(it == mset.end()) [[unlikely]] throw invalid_argument("erase_single(): why v not in mset!?!?"); return mset.erase(it); } void solve(); // template end #endif int main(void) { cin.tie(nullptr); ios::sync_with_stdio(false); ll t = 1; // cin >> t; times(t) solve(); return 0; } using mat55 = array<array<mint, 5>, 5>; mat55 matmul(const mat55 &a, const mat55 &b) { mat55 res{}; for(intmax_t i = 0; i < intmax_t(5); i++) { ranges::fill(res[i], 0); } for(intmax_t i = 0; i < intmax_t(5); i++) { for(intmax_t j = 0; j < intmax_t(5); j++) { for(intmax_t k = 0; k < intmax_t(5); k++) { res[i][j] += a[i][k] * b[k][j]; } } } return res; } void solve() { mint a, b, c, d, e; cin >> a >> b >> c >> d >> e; ll n; cin >> n; if(n == 0) { cout << a << lf; return; } mat55 m{}; for(intmax_t i = 0; i < intmax_t(5); i++) { ranges::fill(m[i], 0); } m[0][0] = m[0][1] = m[1][4] = m[2][1] = m[3][2] = m[4][4] = 1; m[1][1] = c; m[1][2] = d; mat55 mn{}; for(intmax_t i = 0; i < intmax_t(5); i++) { ranges::fill(mn[i], 0); } for(intmax_t i = 0; i < intmax_t(5); i++) { mn[i][i] = 1; } n -= 1; whlie(n) { if(n % 2) mn = matmul(mn, m); m = matmul(m, m); n /= 2; } array<mint, 5> v; v[2] = b; v[3] = a; v[0] = v[2] + v[3]; v[1] = c * v[2] + d * v[3] + e; v[4] = e; mint ans = 0; for(intmax_t i = 0; i < intmax_t(5); i++) { ans += mn[0][i] * v[i]; } out(mn[0], sp, clog), clog << lf; out(v, sp, clog), clog << lf; cout << ans << lf; }