#line 1 "test/01_Math/03_Algebra/01.01.02.01_yukicoder-194.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/194" #line 1 "template/template.hpp" #include #define int int64_t using namespace std; #line 3 "01_Math/02_Combinatorics/01.01_mod-operation.hpp" /** * @brief mod 上の基本演算 */ template inline M mod(T a, M m) { return (a % m + m) % m; } template inline M add(T a, U b, M m) { return mod(mod(a, m) + mod(b, m), m); } template inline M sub(T a, U b, M m) { return mod(mod(a, m) - mod(b, m), m); } template inline M mul(T a, U b, M m) { return mod((__uint128_t)a * b, m); } #line 3 "01_Math/02_Combinatorics/01.02.00_modint-base.hpp" #include /** * @brief modint 構造体 (base) */ class modint_base {}; template using is_modint = std::is_base_of; #line 3 "01_Math/02_Combinatorics/01.03.02_mod-pow.big-mod.hpp" /** * @brief 累乗 : $a^n\bmod{m}$ ($m$ が大きい場合) * @note O(log(n)) */ std::uint64_t mod_pow(std::int64_t a, std::uint64_t n, std::uint64_t m) { a = mod(a, m); std::uint64_t res = 1; while (n) { if (n & 1) res = mul(res, a, m); a = mul(a, a, m); n >>= 1; } return res; } #line 5 "01_Math/01_NumberTheory/01.04.01_ext-gcd.hpp" /** * @brief 拡張ユークリッドの互除法 * @note O(min(log(a),log(b))) */ template Integer1 ext_gcd(Integer1 a, Integer2 b, Integer3& x, Integer3& y) { static_assert(std::is_integral::value); static_assert(std::is_integral::value); static_assert(std::is_integral::value || std::is_same::value); if (b == 0) { x = 1; y = 0; return a; } auto g = ext_gcd(b, a % b, y, x); y -= a / b * x; return g; } #line 4 "01_Math/02_Combinatorics/01.04.03_mod-inv.ext-gcd.hpp" /** * @brief 逆元 : $a^{-1}\bmod{m}$ (拡張ユークリッドの互助法) * @note O(log(m)) * @warning a と m は互いに素 */ std::uint64_t mod_inv(std::int64_t a, std::uint64_t m) { __int128_t x, y; auto g = ext_gcd(a, m, x, y); assert(g == 1); return mod(x, m); } #line 7 "01_Math/02_Combinatorics/01.02.01_modint.static.hpp" /** * @brief modint 構造体 (静的 MOD) */ template class static_modint : public modint_base { using mint = static_modint; public: static_modint() = default; template static_modint(const Integer& v) : _v((v % MOD + MOD) % MOD) {} std::uint32_t get_mod() const { return MOD; } std::uint32_t get_val() const { return _v; } template mint& operator += (const Integer& rhs) { _v = add(_v, mint(rhs)._v, MOD); return *this; } template mint& operator -= (const Integer& rhs) { _v = sub(_v, mint(rhs)._v, MOD); return *this; } template mint& operator *= (const Integer& rhs) { _v = mul(_v, mint(rhs)._v, MOD); return *this; } template mint& operator /= (const Integer& rhs) { return *this *= mint(rhs).inv(); } template mint& operator = (const Integer& v) { static_assert(std::is_integral::value); _v = mod(v, MOD); return *this; } mint pow(std::uint32_t n) const { return mint(mod_pow(_v, n, MOD)); } mint inv() const { return mint(mod_inv(_v, MOD)); } mint operator - () const { return mint(_v ? MOD - _v : 0); } friend std::ostream& operator << (std::ostream& os, const static_modint& rhs) { return os << rhs._v; }; friend std::istream& operator >> (std::istream& is, static_modint& rhs) { is >> rhs._v; rhs._v = mod(rhs._v, MOD); return is; } protected: std::uint32_t _v; }; using modint998244353 = static_modint<998244353>; using modint1000000007 = static_modint<1000000007>; template const static_modint operator + (const static_modint& lhs, const static_modint& rhs) { return static_modint(lhs) += rhs; } template const static_modint operator + (const static_modint& lhs, const Integer& rhs) { return static_modint(lhs) += rhs; } template const static_modint operator + (const Integer& lhs, const static_modint& rhs) { return static_modint(rhs) += lhs; } template const static_modint operator - (const static_modint& lhs, const static_modint& rhs) { return static_modint(lhs) -= rhs; } template const static_modint operator - (const static_modint& lhs, const Integer& rhs) { return static_modint(lhs) -= rhs; } template const static_modint operator - (const Integer& lhs, const static_modint& rhs) { return static_modint(rhs) -= lhs; } template const static_modint operator * (const static_modint& lhs, const static_modint& rhs) { return static_modint(lhs) *= rhs; } template const static_modint operator * (const static_modint& lhs, const Integer& rhs) { return static_modint(lhs) *= rhs; } template const static_modint operator * (const Integer& lhs, const static_modint& rhs) { static_assert(std::is_same>::value == false); return static_modint(rhs) *= lhs; } template const static_modint operator / (const static_modint& lhs, const static_modint& rhs) { return static_modint(lhs) /= rhs; } template const static_modint operator / (const static_modint& lhs, const Integer& rhs) { return static_modint(lhs) /= rhs; } template const static_modint operator / (const Integer& lhs, const static_modint& rhs) { return static_modint(rhs) /= lhs; } #line 3 "01_Math/03_Algebra/01.01.00_matrix-base.hpp" /** * @brief 行列 (base) */ class matrix_base {}; template using is_matrix = std::is_base_of; #line 7 "01_Math/03_Algebra/01.01.01.01_matrix.vector.hpp" /** * @brief 行列 (vector) */ template class matrix_vector : matrix_base { public: using value_type = T; matrix_vector() = default; explicit matrix_vector(std::uint32_t n, std::uint32_t m, T x = T(0)) { init(n, m, x); } std::uint32_t height() const { return _n; } std::uint32_t width() const { return _m; } void fill(T x = T(0)) { _v.clear(); _v.assign(_n, std::vector(_m, x)); } void init(std::uint32_t n, std::uint32_t m, T x = T(0)) { _n = n; _m = m; fill(x); } const std::vector& operator [] (std::uint32_t i) const { return (_v.at(i)); } std::vector& operator [] (std::uint32_t i) { return (_v.at(i)); } friend std::ostream& operator << (std::ostream& os, const matrix_vector& A) { for (std::uint32_t i = 0; i < A.height(); ++i) for (std::uint32_t j = 0; j < A.width(); ++j) { os << A[i][j] << " \n"[j + 1 == A.width()]; } return os; } protected: std::uint32_t _n, _m; std::vector> _v; }; template matrix_vector operator + (const matrix_vector& A, const T& x) { matrix_vector res(A.height(), A.width()); for (std::uint32_t i = 0; i < A.height(); ++i) for (std::uint32_t j = 0; j < A.width(); ++j) { res[i][j] = A[i][j] + x; } return res; } template matrix_vector operator + (const T& x, const matrix_vector& A) { matrix_vector res(A.height(), A.width()); for (std::uint32_t i = 0; i < A.height(); ++i) for (std::uint32_t j = 0; j < A.width(); ++j) { res[i][j] = x + A[i][j]; } return res; } template matrix_vector operator + (const matrix_vector& A, const matrix_vector& B) { assert(A.height() == B.height() && A.width() == B.width()); matrix_vector res(A.height(), A.width()); for (std::uint32_t i = 0; i < A.height(); ++i) for (std::uint32_t j = 0; j < A.width(); ++j) { res[i][j] = A[i][j] + B[i][j]; } return res; } template matrix_vector operator - (const matrix_vector& A, const T& x) { matrix_vector res(A.height(), A.width()); for (std::uint32_t i = 0; i < A.height(); ++i) for (std::uint32_t j = 0; j < A.width(); ++j) { res[i][j] = A[i][j] - x; } return res; } template matrix_vector operator - (const T& x, const matrix_vector& A) { matrix_vector res(A.height(), A.width()); for (std::uint32_t i = 0; i < A.height(); ++i) for (std::uint32_t j = 0; j < A.width(); ++j) { res[i][j] = x - A[i][j]; } return res; } template matrix_vector operator - (const matrix_vector& A, const matrix_vector& B) { assert(A.height() == B.height() && A.width() == B.width()); matrix_vector res(A.height(), A.width()); for (std::uint32_t i = 0; i < A.height(); ++i) for (std::uint32_t j = 0; j < A.width(); ++j) { res[i][j] = A[i][j] - B[i][j]; } return res; } template matrix_vector operator * (const matrix_vector& A, const T& x) { matrix_vector res(A.height(), A.width()); for (std::uint32_t i = 0; i < A.height(); ++i) for (std::uint32_t j = 0; j < A.width(); ++j) { res[i][j] = A[i][j] * x; } return res; } template matrix_vector operator * (const T& x, const matrix_vector& A) { matrix_vector res(A.height(), A.width()); for (std::uint32_t i = 0; i < A.height(); ++i) for (std::uint32_t j = 0; j < A.width(); ++j) { res[i][j] = x * A[i][j]; } return res; } template std::vector operator * (const matrix_vector& A, const std::vector& v) { assert(A.width() == (std::uint32_t)v.size()); std::vector u(A.height(), T(0)); for (std::uint32_t i = 0; i < A.height(); ++i) for (std::uint32_t j = 0; j < A.width(); ++j) { u[i] = u[i] + A[i][j] * v[j]; } return u; } template matrix_vector operator * (const matrix_vector& A, const matrix_vector& B) { assert(A.width() == B.height()); matrix_vector res(A.height(), B.width(), T(0)); for (std::uint32_t i = 0; i < A.height(); ++i) for (std::uint32_t j = 0; j < B.width(); ++j) for (std::uint32_t k = 0; k < A.width(); ++k) { res[i][j] = res[i][j] + A[i][k] * B[k][j]; } return res; } template matrix_vector operator / (const matrix_vector& A, const T& x) { matrix_vector res(A.height(), A.width()); for (std::uint32_t i = 0; i < A.height(); ++i) for (std::uint32_t j = 0; j < A.width(); ++j) { res[i][j] = A[i][j] / x; } return res; } template matrix_vector operator ^ (matrix_vector A, std::uint64_t n) { assert(A.height() == A.width()); matrix_vector B(A.height(), A.width()); for (int i = 0; i < A.height(); ++i) B[i][i] = T(1); while (n) { if (n & 1) B = B * A; A = A * A; n >>= 1; } return B; } #line 5 "test/01_Math/03_Algebra/01.01.02.01_yukicoder-194.test.cpp" signed main() { int N, K; cin >> N >> K; vector A(N); for (int i = 0; i < N; ++i) cin >> A[i]; if (N <= 10000 && K <= 1000000) { vector fib(K); for (int i = 0; i < N; ++i) { fib[i] = A[i]; fib[N] += A[i]; } for (int i = N + 1; i < K; ++i) { fib[i] += fib[i - 1] * 2; fib[i] -= fib[i - N - 1]; } modint1000000007 sum(0); for (int i = 0; i < K; ++i) { sum += fib[i]; } cout << fib[K - 1] << " " << sum << endl; } else { matrix_vector M(N + 1, N + 1); for (int i = 0; i < N - 1; ++i) { for (int j = 0; j < N + 1; ++j) { if (j == i + 1) M[i][j] = 1; else M[i][j] = 0; } } for (int j = 0; j < N; ++j) { M[N - 1][j] = M[N][j] = 1; } M[N][N] = 1; M = M ^ (K - N); vector v(N + 1); for (int i = 0; i < N; ++i) { v[i] = A[i]; v[N] += A[i]; } auto w = M * v; cout << w[N - 1] << " " << w[N] << endl; } }