結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー |
![]() |
提出日時 | 2019-09-20 21:30:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 9,124 bytes |
コンパイル時間 | 816 ms |
コンパイル使用メモリ | 79,440 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 16:26:59 |
合計ジャッジ時間 | 2,018 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
//#define NDEBUG#include <cstddef>#include <cstdint>#include <iostream>#include <iterator>#include <vector>namespace n91 {using i8 = std::int_fast8_t;using i32 = std::int_fast32_t;using i64 = std::int_fast64_t;using u8 = std::uint_fast8_t;using u32 = std::uint_fast32_t;using u64 = std::uint_fast64_t;using isize = std::ptrdiff_t;using usize = std::size_t;constexpr usize operator"" _z(unsigned long long x) noexcept {return static_cast<usize>(x);}template <class T> class integral_iterator {public:using difference_type = T;using value_type = T;using pointer = const value_type *;using reference = value_type;using iterator_category = std::random_access_iterator_tag;private:using self_type = integral_iterator<value_type>;value_type i;public:constexpr integral_iterator() noexcept : i() {}explicit constexpr integral_iterator(const value_type i) noexcept : i(i) {}constexpr self_type operator++(int) noexcept { return self_type(i++); }constexpr self_type operator--(int) noexcept { return self_type(i--); }constexpr self_type operator[](const difference_type rhs) const noexcept {return self_type(i + rhs);}constexpr self_type &operator++() noexcept {++i;return *this;}constexpr self_type &operator--() noexcept {--i;return *this;}constexpr reference operator*() const noexcept { return i; }constexpr self_type operator+(const difference_type rhs) const noexcept {return self_type(i + rhs);}constexpr self_type operator-(const difference_type rhs) const noexcept {return self_type(i - rhs);}constexpr difference_type operator-(const self_type rhs) const noexcept {return i - rhs.i;}constexpr bool operator<(const self_type rhs) const noexcept {return i < rhs.i;}constexpr bool operator<=(const self_type rhs) const noexcept {return i <= rhs.i;}constexpr bool operator>(const self_type rhs) const noexcept {return i > rhs.i;}constexpr bool operator>=(const self_type rhs) const noexcept {return i >= rhs.i;}constexpr bool operator==(const self_type rhs) const noexcept {return i == rhs.i;}constexpr bool operator!=(const self_type rhs) const noexcept {return i != rhs.i;}constexpr self_type &operator+=(const difference_type rhs) noexcept {i += rhs;return *this;}constexpr self_type &operator-=(const difference_type rhs) noexcept {i -= rhs;return *this;}};template <class T>constexpr integral_iterator<T> make_int_itr(const T i) noexcept {return integral_iterator<T>(i);}class rep {const usize f, l;public:constexpr rep(const usize f, const usize l) noexcept : f(f), l(l) {}constexpr auto begin() const noexcept { return make_int_itr(f); }constexpr auto end() const noexcept { return make_int_itr(l); }};class revrep {const usize f, l;public:revrep(const usize f, const usize l) noexcept : f(l), l(f) {}auto begin() const noexcept {return std::make_reverse_iterator(make_int_itr(f));}auto end() const noexcept {return std::make_reverse_iterator(make_int_itr(l));}};template <class T> auto md_vec(const usize n, const T &value) {return std::vector<T>(n, value);}template <class... Args> auto md_vec(const usize n, Args... args) {return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));}template <class T> constexpr T difference(const T &a, const T &b) {return a < b ? b - a : a - b;}template <class T> T scan() {T ret;std::cin >> ret;return ret;}} // namespace n91#include <algorithm>#include <array>#include <cassert>#include <cstddef>#include <initializer_list>namespace n91 {template <class T, std::size_t M, std::size_t N>class array_matrix : public std::array<std::array<T, N>, M> {public:array_matrix() {std::for_each(this->begin(), this->end(), [](auto &row) {std::fill(row.begin(), row.end(), static_cast<T>(0));});}array_matrix(std::initializer_list<std::initializer_list<T>> il) {assert(il.size() == M);auto ar_itr = this->begin();const auto ar_end = this->end();auto il_itr = il.begin();while (ar_itr != ar_end) {assert(il_itr->size() == N);std::copy(il_itr->begin(), il_itr->end(), ar_itr->begin());++ar_itr;++il_itr;}}array_matrix &operator*=(const array_matrix<T, N, N> &rhs) {return *this = *this * rhs;}};template <class T, std::size_t L, std::size_t M, std::size_t N>array_matrix<T, L, N> operator*(const array_matrix<T, L, M> &lhs,const array_matrix<T, M, N> &rhs) {array_matrix<T, L, N> ret = {};for (std::size_t i = static_cast<std::size_t>(0); i != L; ++i) {for (std::size_t j = static_cast<std::size_t>(0); j != M; ++j) {for (std::size_t k = static_cast<std::size_t>(0); k != N; ++k) {ret[i][k] += lhs[i][j] * rhs[j][k];}}}return ret;}template <class T, std::size_t N> array_matrix<T, N, N> matrix_identity() {array_matrix<T, N, N> ret;for (std::size_t i = static_cast<std::size_t>(0); i != N; ++i) {ret[i][i] = static_cast<T>(1);}return ret;}} // namespace n91#include <cstdint>namespace n91 {constexpr std::uint_fast64_t totient(std::uint_fast64_t x) noexcept {using u64 = std::uint_fast64_t;u64 ret = x;for (u64 i = static_cast<u64>(2); i * i <= x; ++i) {if (x % i == static_cast<u64>(0)) {ret -= ret / i;x /= i;while (x % i == static_cast<u64>(0)) {x /= i;}}}if (x != static_cast<u64>(1)) {ret -= ret / x;}return ret;}template <std::uint_fast64_t Modulus,std::uint_fast64_t InverseExp =totient(Modulus) - static_cast<std::uint_fast64_t>(1)>class modint {using u64 = std::uint_fast64_t;static_assert(Modulus < static_cast<u64>(1) << static_cast<u64>(32),"Modulus must be less than 2**32");u64 a;constexpr modint &negate() noexcept {if (a != static_cast<u64>(0)) {a = Modulus - a;}return *this;}public:constexpr modint(const u64 x = static_cast<u64>(0)) noexcept: a(x % Modulus) {}constexpr u64 &value() noexcept { return a; }constexpr const u64 &value() const noexcept { return a; }constexpr modint operator+() const noexcept { return modint(*this); }constexpr modint operator-() const noexcept { return modint(*this).negate(); }constexpr modint operator+(const modint rhs) const noexcept {return modint(*this) += rhs;}constexpr modint operator-(const modint rhs) const noexcept {return modint(*this) -= rhs;}constexpr modint operator*(const modint rhs) const noexcept {return modint(*this) *= rhs;}constexpr modint operator/(const modint rhs) const noexcept {return modint(*this) /= rhs;}constexpr modint &operator+=(const modint rhs) noexcept {a += rhs.a;if (a >= Modulus) {a -= Modulus;}return *this;}constexpr modint &operator-=(const modint rhs) noexcept {if (a < rhs.a) {a += Modulus;}a -= rhs.a;return *this;}constexpr modint &operator*=(const modint rhs) noexcept {a = a * rhs.a % Modulus;return *this;}constexpr modint &operator/=(modint rhs) noexcept {u64 exp = InverseExp;while (exp) {if (exp % static_cast<u64>(2) != static_cast<u64>(0)) {*this *= rhs;}rhs *= rhs;exp /= static_cast<u64>(2);}return *this;}constexpr bool operator==(const modint rhs) const noexcept {return a == rhs.a;}constexpr bool operator!=(const modint rhs) const noexcept {return a != rhs.a;}};template <class T, std::uint_fast64_t v> class modint_constant {public:static constexpr T value = static_cast<T>(v);using value_type = T;};} // namespace n91#include <functional>#include <utility>namespace n91 {template <class T, class U, class Operate = std::multiplies<T>>constexpr T power(T base, U exp, const Operate &oper = Operate(),T iden = static_cast<T>(1)) {while (exp != static_cast<U>(0)) {if (exp % static_cast<U>(2) != static_cast<U>(0)) {iden = oper(iden, base);}exp /= static_cast<U>(2);base = oper(base, base);}return iden;}} // namespace n91#include <algorithm>#include <iostream>#include <utility>namespace n91 {void main_() {using mint = modint<static_cast<u64>(1000000007)>;using mat = array_matrix<mint, 2_z, 2_z>;const mint a = static_cast<mint>(scan<u64>());const mint b = static_cast<mint>(scan<u64>());const u64 n = scan<u64>();mat step = {{a, static_cast<mint>(1)}, {b, static_cast<mint>(0)}};array_matrix<mint, 1_z, 2_z> init = {{static_cast<mint>(1), static_cast<mint>(0)}};std::cout << (init * power(step, n, std::multiplies<mat>(),matrix_identity<mint, 2_z>()))[0_z][1_z].value()<< std::endl;}} // namespace n91int main() {n91::main_();return 0;}