test/yukicoder/194/main.test.cpp
Depends on
Code
#define PROBLEM "https://yukicoder.me/problems/no/194"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include "Mylib/IO/input_vector.cpp"
#include "Mylib/LinearAlgebra/inverse_matrix.cpp"
#include "Mylib/LinearAlgebra/square_matrix.cpp"
#include "Mylib/Number/Mint/mint.cpp"
namespace hl = haar_lib;
using mint = hl::modint<1000000007>;
static int N;
using M = hl::square_matrix_dyn<mint, N>;
std::pair<mint, mint> solve1(int64_t N, int64_t K, std::vector<int> A) {
M m;
for (int i = 0; i < N; ++i) m[0][i] = 1;
for (int i = 0; i < N - 1; ++i) m[i + 1][i] = 1;
std::reverse(A.begin(), A.end());
mint f = 0;
{
auto m2 = m.pow(K - N);
for (int i = 0; i < N; ++i) f += m2[0][i] * A[i];
}
mint s = std::accumulate(A.begin(), A.end(), mint(0));
{
auto c = hl::inverse_matrix(M::unit() - m).value();
auto temp = (M::unit() - m.pow(K - N + 1)) * c - M::unit();
s += dot(temp[0], M::vector_type(A));
}
return {f, s};
}
std::pair<mint, mint> solve2(int64_t N, int64_t K, std::vector<int> A) {
std::vector<mint> v(K);
mint temp = 0;
for (int i = 0; i < N; ++i) {
temp += A[i];
v[i] = A[i];
}
for (int i = N; i < K; ++i) {
v[i] = temp;
temp += v[i];
temp -= v[i - N];
}
mint f = v.back();
mint s = std::accumulate(v.begin(), v.end(), mint(0));
return {f, s};
}
int main() {
int64_t K;
std::cin >> N >> K;
auto A = hl::input_vector<int>(N);
auto [f, s] = K > 1000000 ? solve1(N, K, A) : solve2(N, K, A);
std::cout << f << " " << s << "\n";
return 0;
}
#line 1 "test/yukicoder/194/main.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/194"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#line 4 "Mylib/IO/input_vector.cpp"
namespace haar_lib {
template <typename T>
std::vector<T> input_vector(int N) {
std::vector<T> ret(N);
for (int i = 0; i < N; ++i) std::cin >> ret[i];
return ret;
}
template <typename T>
std::vector<std::vector<T>> input_vector(int N, int M) {
std::vector<std::vector<T>> ret(N);
for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
return ret;
}
} // namespace haar_lib
#line 2 "Mylib/LinearAlgebra/inverse_matrix.cpp"
#include <optional>
#include <utility>
namespace haar_lib {
template <typename M>
std::optional<M> inverse_matrix(M m) {
using T = typename M::value_type;
const int N = m.size();
M ret = M::unit();
for (int i = 0; i < N; ++i) {
int p = i;
for (int j = i; j < N; ++j) {
if (m[i][j] != 0) {
p = j;
break;
}
}
std::swap(m[i], m[p]);
std::swap(ret[i], ret[p]);
{
T d = m[i][i];
if (d == 0) return std::nullopt;
for (int j = 0; j < N; ++j) {
m[i][j] /= d;
ret[i][j] /= d;
}
}
for (int j = 0; j < N; ++j) {
if (i == j) continue;
T d = m[j][i] / m[i][i];
for (int k = 0; k < N; ++k) {
m[j][k] -= m[i][k] * d;
ret[j][k] -= ret[i][k] * d;
}
}
}
return ret;
}
} // namespace haar_lib
#line 2 "Mylib/LinearAlgebra/square_matrix.cpp"
#include <cstdint>
#line 6 "Mylib/LinearAlgebra/square_matrix.cpp"
namespace haar_lib {
template <typename T, int &N>
class vector_dyn {
public:
using value_type = T;
private:
std::vector<T> data_;
public:
vector_dyn() : data_(N) {}
vector_dyn(T value) : data_(N, value) {}
vector_dyn(std::initializer_list<T> list) : data_(N) {
int i = 0;
for (auto it = list.begin(); it != list.end(); ++it) data_[i++] = *it;
}
vector_dyn(const vector_dyn &that) : data_(that.data_) {}
template <typename U>
vector_dyn(const std::vector<U> &that) : data_(that.begin(), that.end()) {}
bool operator==(const vector_dyn &that) { return data_ == that.data_; }
bool operator!=(const vector_dyn &that) { return !(*this == that); }
auto &operator=(const vector_dyn &that) {
data_ = that.data_;
return *this;
}
auto &operator+=(const vector_dyn &that) {
for (int i = 0; i < N; ++i) data_[i] += that.data_[i];
return *this;
}
auto &operator-=(const vector_dyn &that) {
for (int i = 0; i < N; ++i) data_[i] -= that.data_[i];
return *this;
}
friend auto dot(const vector_dyn &a, const vector_dyn &b) {
T ret = 0;
for (int i = 0; i < N; ++i) ret += a.data_[i] * b.data_[i];
return ret;
}
auto operator+(const vector_dyn &that) const {
return vector(*this) += that;
}
auto operator-(const vector_dyn &that) const {
return vector(*this) -= that;
}
auto &operator[](int i) { return data_[i]; }
const auto &operator[](int i) const { return data_[i]; }
auto begin() const { return data_.begin(); }
auto end() const { return data_.end(); }
int size() const { return N; }
friend std::ostream &operator<<(std::ostream &s, const vector_dyn &a) {
s << "{";
for (auto it = a.data_.begin(); it != a.data_.end(); ++it) {
if (it != a.data_.begin()) s << ",";
s << *it;
}
s << "}";
return s;
}
};
template <typename T, int &N>
class square_matrix_dyn {
public:
using value_type = T;
using vector_type = vector_dyn<T, N>;
private:
std::vector<vector_type> data_;
public:
square_matrix_dyn() : data_(N, vector_type()) {}
square_matrix_dyn(const T &val) : data_(N, vector_type(val)) {}
square_matrix_dyn(std::initializer_list<std::initializer_list<T>> list) : data_(N) {
int i = 0;
for (auto it = list.begin(); it != list.end(); ++it) {
data_[i++] = vector_type(*it);
}
}
square_matrix_dyn(const square_matrix_dyn &that) : data_(that.data_) {}
square_matrix_dyn(const std::vector<std::vector<T>> &that) : data_(N) {
for (int i = 0; i < N; ++i) data_[i] = that[i];
}
bool operator==(const square_matrix_dyn &that) const { return data_ == that.data_; }
bool operator!=(const square_matrix_dyn &that) const { return !(*this == that); }
auto &operator=(const square_matrix_dyn &that) {
data_ = that.data_;
return *this;
}
auto &operator+=(const square_matrix_dyn &that) {
for (int i = 0; i < N; ++i) data_[i] += that.data_[i];
return *this;
}
auto &operator-=(const square_matrix_dyn &that) {
for (int i = 0; i < N; ++i) data_[i] -= that.data_[i];
return *this;
}
auto &operator*=(const square_matrix_dyn &that) {
square_matrix_dyn ret;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
for (int k = 0; k < N; ++k)
ret[i][j] += data_[i][k] * that.data_[k][j];
return *this = ret;
}
const auto &operator[](int i) const { return data_[i]; }
auto &operator[](int i) { return data_[i]; }
int size() const { return N; }
static auto unit() {
square_matrix_dyn ret;
for (int i = 0; i < N; ++i) ret[i][i] = 1;
return ret;
}
auto operator+(const square_matrix_dyn &that) {
return square_matrix_dyn(*this) += that;
}
auto operator-(const square_matrix_dyn &that) {
return square_matrix_dyn(*this) -= that;
}
auto operator*(const square_matrix_dyn &that) {
return square_matrix_dyn(*this) *= that;
}
auto pow(uint64_t p) const {
auto ret = unit();
auto a = *this;
while (p > 0) {
if (p & 1) ret *= a;
a *= a;
p >>= 1;
}
return ret;
}
auto operator*(const vector_type &that) {
vector_type ret;
for (int i = 0; i < N; ++i) ret[i] = dot(data_[i], that);
return ret;
}
};
} // namespace haar_lib
#line 4 "Mylib/Number/Mint/mint.cpp"
namespace haar_lib {
template <int32_t M>
class modint {
uint32_t val_;
public:
constexpr static auto mod() { return M; }
constexpr modint() : val_(0) {}
constexpr modint(int64_t n) {
if (n >= M)
val_ = n % M;
else if (n < 0)
val_ = n % M + M;
else
val_ = n;
}
constexpr auto &operator=(const modint &a) {
val_ = a.val_;
return *this;
}
constexpr auto &operator+=(const modint &a) {
if (val_ + a.val_ >= M)
val_ = (uint64_t) val_ + a.val_ - M;
else
val_ += a.val_;
return *this;
}
constexpr auto &operator-=(const modint &a) {
if (val_ < a.val_) val_ += M;
val_ -= a.val_;
return *this;
}
constexpr auto &operator*=(const modint &a) {
val_ = (uint64_t) val_ * a.val_ % M;
return *this;
}
constexpr auto &operator/=(const modint &a) {
val_ = (uint64_t) val_ * a.inv().val_ % M;
return *this;
}
constexpr auto operator+(const modint &a) const { return modint(*this) += a; }
constexpr auto operator-(const modint &a) const { return modint(*this) -= a; }
constexpr auto operator*(const modint &a) const { return modint(*this) *= a; }
constexpr auto operator/(const modint &a) const { return modint(*this) /= a; }
constexpr bool operator==(const modint &a) const { return val_ == a.val_; }
constexpr bool operator!=(const modint &a) const { return val_ != a.val_; }
constexpr auto &operator++() {
*this += 1;
return *this;
}
constexpr auto &operator--() {
*this -= 1;
return *this;
}
constexpr auto operator++(int) {
auto t = *this;
*this += 1;
return t;
}
constexpr auto operator--(int) {
auto t = *this;
*this -= 1;
return t;
}
constexpr static modint pow(int64_t n, int64_t p) {
if (p < 0) return pow(n, -p).inv();
int64_t ret = 1, e = n % M;
for (; p; (e *= e) %= M, p >>= 1)
if (p & 1) (ret *= e) %= M;
return ret;
}
constexpr static modint inv(int64_t a) {
int64_t b = M, u = 1, v = 0;
while (b) {
int64_t t = a / b;
a -= t * b;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
u %= M;
if (u < 0) u += M;
return u;
}
constexpr static auto frac(int64_t a, int64_t b) { return modint(a) / modint(b); }
constexpr auto pow(int64_t p) const { return pow(val_, p); }
constexpr auto inv() const { return inv(val_); }
friend constexpr auto operator-(const modint &a) { return modint(M - a.val_); }
friend constexpr auto operator+(int64_t a, const modint &b) { return modint(a) + b; }
friend constexpr auto operator-(int64_t a, const modint &b) { return modint(a) - b; }
friend constexpr auto operator*(int64_t a, const modint &b) { return modint(a) * b; }
friend constexpr auto operator/(int64_t a, const modint &b) { return modint(a) / b; }
friend std::istream &operator>>(std::istream &s, modint &a) {
s >> a.val_;
return s;
}
friend std::ostream &operator<<(std::ostream &s, const modint &a) {
s << a.val_;
return s;
}
template <int N>
static auto div() {
static auto value = inv(N);
return value;
}
explicit operator int32_t() const noexcept { return val_; }
explicit operator int64_t() const noexcept { return val_; }
};
} // namespace haar_lib
#line 11 "test/yukicoder/194/main.test.cpp"
namespace hl = haar_lib;
using mint = hl::modint<1000000007>;
static int N;
using M = hl::square_matrix_dyn<mint, N>;
std::pair<mint, mint> solve1(int64_t N, int64_t K, std::vector<int> A) {
M m;
for (int i = 0; i < N; ++i) m[0][i] = 1;
for (int i = 0; i < N - 1; ++i) m[i + 1][i] = 1;
std::reverse(A.begin(), A.end());
mint f = 0;
{
auto m2 = m.pow(K - N);
for (int i = 0; i < N; ++i) f += m2[0][i] * A[i];
}
mint s = std::accumulate(A.begin(), A.end(), mint(0));
{
auto c = hl::inverse_matrix(M::unit() - m).value();
auto temp = (M::unit() - m.pow(K - N + 1)) * c - M::unit();
s += dot(temp[0], M::vector_type(A));
}
return {f, s};
}
std::pair<mint, mint> solve2(int64_t N, int64_t K, std::vector<int> A) {
std::vector<mint> v(K);
mint temp = 0;
for (int i = 0; i < N; ++i) {
temp += A[i];
v[i] = A[i];
}
for (int i = N; i < K; ++i) {
v[i] = temp;
temp += v[i];
temp -= v[i - N];
}
mint f = v.back();
mint s = std::accumulate(v.begin(), v.end(), mint(0));
return {f, s};
}
int main() {
int64_t K;
std::cin >> N >> K;
auto A = hl::input_vector<int>(N);
auto [f, s] = K > 1000000 ? solve1(N, K, A) : solve2(N, K, A);
std::cout << f << " " << s << "\n";
return 0;
}
Back to top page