test/aoj/1327/main.test.cpp
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1327"
#include <iostream>
#include <vector>
#include "Mylib/IO/input_vector.cpp"
#include "Mylib/IO/join.cpp"
#include "Mylib/LinearAlgebra/square_matrix.cpp"
#include "Mylib/Number/Mint/runtime_mint.cpp"
namespace hl = haar_lib;
static int n, m;
using mint = hl::runtime_modint<m>;
using M = hl::square_matrix_dyn<mint, n>;
int main() {
int a, b, c, t;
while (std::cin >> n >> m >> a >> b >> c >> t, n) {
auto s = hl::input_vector<mint>(n);
M mat;
for (int i = 0; i < n; ++i) {
if (i - 1 >= 0) mat[i][i - 1] = a;
mat[i][i] = b;
if (i + 1 < n) mat[i][i + 1] = c;
}
mat = mat.pow(t);
auto ans = mat * M::vector_type(s);
std::cout << hl::join(ans.begin(), ans.end()) << "\n";
}
return 0;
}
#line 1 "test/aoj/1327/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1327"
#include <iostream>
#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 3 "Mylib/IO/join.cpp"
#include <sstream>
#include <string>
namespace haar_lib {
template <typename Iter>
std::string join(Iter first, Iter last, std::string delim = " ") {
std::stringstream s;
for (auto it = first; it != last; ++it) {
if (it != first) s << delim;
s << *it;
}
return s.str();
}
} // namespace haar_lib
#line 2 "Mylib/LinearAlgebra/square_matrix.cpp"
#include <cstdint>
#line 4 "Mylib/LinearAlgebra/square_matrix.cpp"
#include <utility>
#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/runtime_mint.cpp"
namespace haar_lib {
template <const int &M>
class runtime_modint {
int64_t val_;
public:
runtime_modint() : val_(0) {}
runtime_modint(int64_t n) {
if (n >= M)
val_ = n % M;
else if (n < 0)
val_ = n % M + M;
else
val_ = n;
}
static auto mod() { return M; }
auto operator+(const runtime_modint &a) const { return runtime_modint(val_ + a.val_); }
auto operator-(const runtime_modint &a) const { return runtime_modint(val_ - a.val_); }
auto operator*(const runtime_modint &a) const { return runtime_modint(val_ * a.val_); }
auto operator/(const runtime_modint &a) const { return runtime_modint(val_ * a.inv().val_); }
const auto &operator=(const runtime_modint &a) {
val_ = a.val_;
return *this;
}
const auto &operator+=(const runtime_modint &a) {
if ((val_ += a.val_) >= M) val_ -= M;
return *this;
}
const auto &operator-=(const runtime_modint &a) {
if (val_ < a.val_) val_ += M;
val_ -= a.val_;
return *this;
}
const auto &operator*=(const runtime_modint &a) {
(val_ *= a.val_) %= M;
return *this;
}
const auto &operator/=(const runtime_modint &a) {
(val_ *= a.inv().val_) %= M;
return *this;
}
bool operator==(const runtime_modint &a) const { return val_ == a.val_; }
bool operator!=(const runtime_modint &a) const { return val_ != a.val_; }
static auto pow(int64_t n, int64_t p) {
runtime_modint ret = 1, e = n;
for (; p; e *= e, p >>= 1)
if (p & 1) ret *= e;
return ret;
}
auto pow(int64_t p) const {
runtime_modint ret = 1, e = val_;
for (; p; e *= e, p >>= 1)
if (p & 1) ret *= e;
return ret;
}
runtime_modint inv() const {
int64_t a = val_, 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;
}
explicit operator int32_t() const noexcept { return val_; }
explicit operator int64_t() const noexcept { return val_; }
friend auto operator-(const runtime_modint &a) { return runtime_modint(-a.val_); }
friend auto operator+(int64_t a, const runtime_modint &b) { return runtime_modint(a) + b; }
friend auto operator-(int64_t a, const runtime_modint &b) { return runtime_modint(a) - b; }
friend auto operator*(int64_t a, const runtime_modint &b) { return runtime_modint(a) * b; }
friend auto operator/(int64_t a, const runtime_modint &b) { return runtime_modint(a) / b; }
friend std::istream &operator>>(std::istream &is, runtime_modint &a) {
is >> a.val_;
return is;
}
friend std::ostream &operator<<(std::ostream &os, const runtime_modint &a) {
os << a.val_;
return os;
}
};
} // namespace haar_lib
#line 9 "test/aoj/1327/main.test.cpp"
namespace hl = haar_lib;
static int n, m;
using mint = hl::runtime_modint<m>;
using M = hl::square_matrix_dyn<mint, n>;
int main() {
int a, b, c, t;
while (std::cin >> n >> m >> a >> b >> c >> t, n) {
auto s = hl::input_vector<mint>(n);
M mat;
for (int i = 0; i < n; ++i) {
if (i - 1 >= 0) mat[i][i - 1] = a;
mat[i][i] = b;
if (i + 1 < n) mat[i][i + 1] = c;
}
mat = mat.pow(t);
auto ans = mat * M::vector_type(s);
std::cout << hl::join(ans.begin(), ans.end()) << "\n";
}
return 0;
}
Back to top page