This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ageprocpp/competitive-programming-library
#define PROBLEM "https://judge.yosupo.jp/problem/matrix_product" #include "../../basic/template.hpp" #include "../../math/StaticModInt.hpp" #include "../../math/Matrix.hpp" using ModInt = StaticModInt<998244353>; int N, M, K; int main() { scanf("%d%d%d", &N, &M, &K); Matrix<ModInt> mat1(N, M), mat2(M, K); rep(i, N) rep(j, M) std::cin >> mat1[i][j]; rep(i, M) rep(j, K) std::cin >> mat2[i][j]; auto res = mat1 * mat2; rep(i, N) std::cout << res[i] << std::endl; return 0; }
#line 1 "test/yosupo/matrix_product.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/matrix_product" #line 2 "basic/template.hpp" #define _CRT_SECURE_NO_WARNINGS #ifndef __clang__ #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #include <string.h> #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <cfloat> #include <chrono> #include <climits> #include <cmath> #include <complex> #include <ctime> #include <deque> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <iterator> #include <list> #include <map> #include <memory> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> #define rep(i, n) for (int i = 0; i < int(n); i++) #define REP(i, n) for (int i = 1; i <= int(n); i++) #define all(V) V.begin(), V.end() using i128 = __int128_t; using u128 = __uint128_t; using uint = unsigned int; using lint = long long; using ulint = unsigned long long; using IP = std::pair<int, int>; using LP = std::pair<lint, lint>; constexpr int INF = INT_MAX / 2; constexpr lint LINF = LLONG_MAX / 2; constexpr double eps = DBL_EPSILON * 10; constexpr double PI = 3.141592653589793238462643383279; template <class T> class prique : public std::priority_queue<T, std::vector<T>, std::greater<T>> {}; int popcount(uint x) { #if __cplusplus >= 202002L return std::popcount(x); #else #ifndef __clang__ return __builtin_popcount(x); #endif #endif x = (x & 0x55555555) + (x >> 1 & 0x55555555); x = (x & 0x33333333) + (x >> 2 & 0x33333333); x = (x & 0x0f0f0f0f) + (x >> 4 & 0x0f0f0f0f); x = (x & 0x00ff00ff) + (x >> 8 & 0x00ff00ff); return (x & 0x0000ffff) + (x >> 16 & 0x0000ffff); } template <class F> inline constexpr decltype(auto) lambda_fix(F&& f) { return [f = std::forward<F>(f)](auto&&... args) { return f(f, std::forward<decltype(args)>(args)...); }; } template <class T> constexpr std::vector<T> make_vec(size_t n) { return std::vector<T>(n); } template <class T, class... Args> constexpr auto make_vec(size_t n, Args&&... args) { return std::vector<decltype(make_vec<T>(args...))>(n, make_vec<T>(std::forward<Args>(args)...)); } template <class T, class U, class Stream> Stream& operator>>(Stream& ist, std::pair<T, U>& x) { return ist >> x.first >> x.second; } template <class T, class U, class Stream> Stream& operator<<(Stream& ost, const std::pair<T, U>& x) { return ost << x.first << " " << x.second; } template <class Container, std::enable_if_t<!std::is_same<Container, std::string>::value, std::nullptr_t> = nullptr> auto operator>>(std::istream& ist, Container& cont) -> decltype(typename Container::iterator(), std::cin)& { Container tmp; while (true) { typename Container::value_type t; ist >> t; tmp.emplace_back(t); if (getchar() == '\n') break; } cont = Container(std::move(tmp)); return ist; } template <class Container, class Stream, std::enable_if_t<!std::is_same<Container, std::string>::value, std::nullptr_t> = nullptr> auto operator<<(Stream& ost, const Container& cont) -> decltype(typename Container::iterator(), ost)& { for (auto it = cont.begin(); it != cont.end(); it++) { if (it != cont.begin()) ost << ' '; ost << *it; } return ost; } template <class Container> auto sum(const Container& cont) -> decltype(typename Container::iterator(), 0LL) { lint res = 0; for (auto it = cont.begin(); it != cont.end(); it++) res += *it; return res; } template <class T, class U> constexpr inline bool chmax(T& lhs, const U& rhs) noexcept { if (lhs < rhs) { lhs = rhs; return true; } return false; } template <class T, class U> constexpr inline bool chmin(T& lhs, const U& rhs) noexcept { if (lhs > rhs) { lhs = rhs; return true; } return false; } constexpr inline lint gcd(lint a, lint b) noexcept { while (b) { lint c = a; a = b; b = c % b; } return a; } inline lint lcm(lint a, lint b) noexcept { return a / gcd(a, b) * b; } constexpr bool isprime(lint n) noexcept { if (n == 1) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } template <class T> constexpr T mypow(T a, lint b) noexcept { T res(1); while (true) { if (b & 1) res *= a; b >>= 1; if (!b) break; a *= a; } return res; } constexpr lint modpow(lint a, lint b, lint m) noexcept { a %= m; lint res(1); while (b) { if (b & 1) res *= a, res %= m; a *= a, a %= m, b >>= 1; } return res; } LP extGcd(lint a, lint b) noexcept { if (b == 0) return {1, 0}; LP s = extGcd(b, a % b); std::swap(s.first, s.second); s.second -= a / b * s.first; return s; } LP ChineseRem(const lint& b1, const lint& m1, const lint& b2, const lint& m2) noexcept { auto p = extGcd(m1, m2); lint g = gcd(m1, m2), l = m1 / g * m2; lint tmp = (b2 - b1) / g * p.first % (m2 / g); lint r = (b1 + m1 * tmp + l) % l; return {r, l}; } int LCS(const std::string& a, const std::string& b) { auto dp = make_vec<int>(a.size() + 1, b.size() + 1); rep(i, a.size()) { rep(j, b.size()) { chmax(dp[i + 1][j], dp[i][j]); chmax(dp[i][j + 1], dp[i][j]); if (a[i] == b[j]) chmax(dp[i + 1][j + 1], dp[i][j] + 1); } chmax(dp[i + 1][b.size()], dp[i][b.size()]); } rep(j, b.size()) chmax(dp[a.size()][j + 1], dp[a.size()][j]); return dp[a.size()][b.size()]; } template <class T, std::enable_if_t<std::is_convertible<int, T>::value, std::nullptr_t> = nullptr> void compress(std::vector<T>& vec) { auto tmp = vec; std::sort(all(tmp)); tmp.erase(std::unique(all(tmp)), tmp.end()); for (T& i : vec) i = std::lower_bound(all(tmp), i) - tmp.begin(); } template <class T> void compress(T* l, T* r) { std::vector<T> tmp(l, r); std::sort(all(tmp)); tmp.erase(std::unique(all(tmp)), tmp.end()); for (auto i = l; i < r; i++) { *i = std::lower_bound(all(tmp), *i) - tmp.begin(); } } template <class InputIter> void compress(InputIter l, InputIter r) { std::vector<typename InputIter::value_type> tmp(l, r); std::sort(all(tmp)); tmp.erase(std::unique(all(tmp)), tmp.end()); for (auto i = l; i < r; i++) { *i = std::lower_bound(all(tmp), *i) - tmp.begin(); } } template <class InputIter, std::enable_if_t<std::is_same<typename InputIter::value_type, std::pair<IP, int>>::value, std::nullptr_t> = nullptr> void mo_sort(InputIter l, InputIter r, int N) { const int M = std::max(1.0, std::sqrt(lint(N) * N / std::distance(l, r))); std::sort(l, r, [M](const auto& lhs, const auto& rhs) { if (lhs.first.first / M < rhs.first.first / M) return true; if (lhs.first.first / M == rhs.first.first / M) return lhs.first.second < rhs.first.second; return false; }); int before = -1, cnt = 0; bool f = false; for (InputIter i = l; i != r; i++) { if (before != i->first.first / M) { if (f) std::reverse(i - cnt, i); f ^= true, before = i->first.first / M, cnt = 1; } else cnt++; } if (f) std::reverse(r - cnt, r); } template <class T> std::vector<T> xor_bases(const std::vector<T>& vec) { std::vector<T> res; for (T i : vec) { for (T j : res) { chmin(i, i ^ j); } if (i) res.emplace_back(i); } return res; } #line 3 "basic/type_traits.hpp" class ModInt__Base {}; class StaticModInt__Base : ModInt__Base {}; class DynamicModInt__Base : ModInt__Base {}; template <class T> class is_ModInt : public std::is_base_of<ModInt__Base, T> {}; template <class T> constexpr bool is_ModInt_v = is_ModInt<T>::value; template <class T> class is_StaticModInt : public std::is_base_of<StaticModInt__Base, T> {}; template <class T> constexpr bool is_StaticModInt_v = is_StaticModInt<T>::value; template <class T> class is_DynamicModInt : public std::is_base_of<DynamicModInt__Base, T> {}; template <class T> constexpr bool is_DynamicModInt_v = is_DynamicModInt<T>::value; #line 4 "math/StaticModInt.hpp" template <int modulo> class StaticModInt : StaticModInt__Base { uint value; static constexpr int inv1000000007[] = {0, 1, 500000004, 333333336, 250000002, 400000003, 166666668, 142857144, 125000001, 111111112, 700000005}, inv998244353[] = {0, 1, 499122177, 332748118, 748683265, 598946612, 166374059, 855638017, 873463809, 443664157, 299473306}; public: static constexpr int mod_value = modulo; constexpr StaticModInt() : value(0) {} template <class T, std::enable_if_t<!std::is_convertible<T, StaticModInt>::value, std::nullptr_t> = nullptr> constexpr StaticModInt(T value = 0) : value(value % modulo) { if (this->value < 0) this->value += modulo; } inline constexpr StaticModInt inv() const { if constexpr (modulo == 1000000007) { if (*this <= 10) return inv1000000007[*this]; } else if constexpr (modulo == 998244353) { if (*this <= 10) return inv998244353[*this]; } return mypow(*this, modulo - 2); } inline constexpr StaticModInt pow(lint k) const { return mypow(*this, k); } inline constexpr operator int() const { return value; } inline constexpr StaticModInt& operator+=(const StaticModInt& x) { value = value + x.value; if (value >= modulo) value -= modulo; return *this; } inline constexpr StaticModInt& operator++() { if (value == modulo - 1) value = 0; else value++; return *this; } inline constexpr StaticModInt operator++(int) { StaticModInt res = *this; ++*this; return res; } inline constexpr StaticModInt operator-() const { return StaticModInt(0) -= *this; } inline constexpr StaticModInt& operator-=(const StaticModInt& x) { if (value < x.value) value += modulo; value -= x.value; return *this; } inline constexpr StaticModInt& operator--() { if (value == 0) value = modulo - 1; else value--; return *this; } inline constexpr StaticModInt operator--(int) { StaticModInt res = *this; --*this; return res; } inline constexpr StaticModInt& operator*=(const StaticModInt& x) { value = (ulint)value * x.value % modulo; return *this; } inline constexpr StaticModInt& operator/=(const StaticModInt& rhs) { return *this *= rhs.inv(); } template <class T> constexpr StaticModInt operator+(const T& rhs) const { return StaticModInt(*this) += rhs; } template <class T> constexpr StaticModInt& operator+=(const T& rhs) { return operator+=(StaticModInt(rhs)); } template <class T> constexpr StaticModInt operator-(const T& rhs) const { return StaticModInt(*this) -= rhs; } template <class T> constexpr StaticModInt& operator-=(const T& rhs) { return operator-=(StaticModInt(rhs)); } template <class T> constexpr StaticModInt operator*(const T& rhs) const { return StaticModInt(*this) *= rhs; } template <class T> constexpr StaticModInt& operator*=(const T& rhs) { return operator*=(StaticModInt(rhs)); } template <class T> constexpr StaticModInt operator/(const T& rhs) const { return StaticModInt(*this) /= rhs; } template <class T> constexpr StaticModInt& operator/=(const T& rhs) { return operator/=(StaticModInt(rhs)); } static StaticModInt primitive_root() { if constexpr (modulo == 1012924417) return 5; if constexpr (modulo == 924844033) return 5; if constexpr (modulo == 998244353) return 3; if constexpr (modulo == 1224736769) return 3; if constexpr (modulo == 167772161) return 3; if constexpr (modulo == 469762049) return 3; if constexpr (modulo == 1107296257) return 10; int p = 0; std::mt19937 mt(0); std::uniform_int_distribution<> uid(1, modulo - 1); if (p) return p; // use naive factorize due to file size limit std::vector<int> vec; int tmp = modulo - 1; for (int i = 2; i * i <= tmp; i++) { if (tmp % i == 0) { vec.emplace_back(i); do { tmp /= i; } while (tmp % i == 0); } } if (tmp != 1) vec.emplace_back(tmp); while (true) { p = uid(mt); bool f = true; for (const auto& i : vec) { if (mypow(StaticModInt(p), (modulo - 1) / i) == 1) { f = false; break; } } if (f) return p; } } }; template <int modulo, class Stream> Stream& operator>>(Stream& ist, StaticModInt<modulo>& x) { lint a; ist >> a; x = a; return ist; } template <int modulo, class Stream> Stream& operator<<(Stream& ost, const StaticModInt<modulo>& x) { ost << int(x); return ost; } #if __cplusplus < 201703L template <int modulo> constexpr int StaticModInt<modulo>::inv1000000007[]; template <int modulo> constexpr int StaticModInt<modulo>::inv998244353[]; #endif /** * @title StaticModInt */ #line 3 "math/Matrix.hpp" template <class T, std::enable_if_t< #if __cplusplus >= 201703L std::is_same_v<decltype(T() / T()), T> #else std::is_same<decltype(T() / T()), T>::value #endif , std::nullptr_t> = nullptr> class Matrix { protected: uint N, M; std::vector<std::vector<T>> elems; public: Matrix() = default; Matrix(uint N_, uint M_) : N(N_), M(M_), elems(N, std::vector<T>(M)) {} std::vector<T>& operator[](uint idx) { return elems[idx]; } const std::vector<T>& operator[](uint idx) const { return elems[idx]; } decltype(elems)& data() { return elems; } const decltype(elems)& data() const { return elems; } void resize(int N_, int M_) { elems.resize(N_); rep(i, N_) elems[i].resize(M_); } Matrix operator*(Matrix rhs) const { Matrix<T> res(N, rhs.M); rep(i, N) rep(j, M) rep(k, rhs.M) res[i][k] += elems[i][j] * rhs.elems[j][k]; return res; } }; template <class T> class SquareMatrix : public Matrix<T> { using Matrix<T>::N; using Matrix<T>::Matrix; using Matrix<T>::elems; public: SquareMatrix(uint N_) : Matrix<T>(N_, N_) {} SquareMatrix<T>& operator=(const Matrix<T>& rhs) { elems = rhs.data(); return *this; } SquareMatrix<T>& operator=(Matrix<T>&& rhs) { elems = std::move(rhs.data()); return *this; } SquareMatrix<T> operator*=(const SquareMatrix<T>& rhs) { *this = *this * rhs; return *this; } SquareMatrix<T> pow(lint p) const { SquareMatrix<T> res{N}, memo = *this; rep(i, N) res[i][i] = 1; while (p) { if (p & 1) res *= memo; p >>= 1; memo *= memo; } return res; } constexpr T determinant() const { SquareMatrix<T> tmp = *this; T res(1); rep(i, N) { if (tmp[i][i] == 0) { for (int j = i + 1; j < N; j++) { if (tmp[j][i]) { std::swap(tmp[i], tmp[j]); res = -res; break; } } } res *= tmp[i][i]; for (int j = i + 1; j < N; j++) { T inv = T(1) / tmp[i][i]; for (int k = i + 1; k < N; k++) { tmp[j][k] -= tmp[j][i] * inv * tmp[i][k]; } } } return res; } }; template <class T, uint N, uint M> class FixedMatrix { protected: std::array<std::array<T, M>, N> elems; public: constexpr FixedMatrix() { rep(i, N) elems[i].fill(0); } constexpr FixedMatrix(std::initializer_list<T> init) { auto ite = init.begin(); rep(i, N) rep(j, M) elems[i][j] = *ite++; } constexpr FixedMatrix(const FixedMatrix<T, N, M>& rhs) { elems = rhs.elems; } constexpr FixedMatrix(FixedMatrix<T, N, M>&& rhs) { elems = std::move(rhs.elems); } constexpr std::array<T, N>& operator[](uint idx) { return elems[idx]; } constexpr const std::array<T, N>& operator[](uint idx) const { return elems[idx]; } constexpr decltype(elems)& data() { return elems; } constexpr const decltype(elems)& data() const { return elems; } constexpr FixedMatrix<T, N, M> operator=(const FixedMatrix<T, N, M>& rhs) { elems = rhs.elems; return *this; } constexpr FixedMatrix<T, N, M> operator=(FixedMatrix<T, N, M>&& rhs) { elems = std::move(rhs.elems); return *this; } constexpr FixedMatrix<T, N, M> operator+=(const FixedMatrix<T, N, M>& rhs) { rep(i, N) rep(j, M) elems[i][j] += rhs.elems[i][j]; return *this; } constexpr FixedMatrix<T, N, M> operator+( const FixedMatrix<T, N, M>& rhs) const { FixedMatrix<T, N, M> res = *this; return res += rhs; } template <uint L> constexpr FixedMatrix<T, N, L> operator*( const FixedMatrix<T, M, L>& rhs) const { FixedMatrix<T, N, L> res; rep(i, N) rep(j, M) rep(k, L) res[i][k] += elems[i][j] * rhs.elems[j][k]; return res; } }; template <class T, uint N> class FixedSquareMatrix : public FixedMatrix<T, N, N> { using FixedMatrix<T, N, N>::FixedMatrix; using FixedMatrix<T, N, N>::elems; public: using FixedMatrix<T, N, N>::operator*; constexpr FixedSquareMatrix(const FixedMatrix<T, N, N>& obj) : FixedMatrix<T, N, N>(obj) {} constexpr FixedSquareMatrix(FixedMatrix<T, N, N>&& obj) : FixedMatrix<T, N, N>(obj) {} constexpr FixedSquareMatrix<T, N>& operator*=( const FixedSquareMatrix<T, N>& rhs) { *this = *this * rhs; return *this; } constexpr FixedSquareMatrix<T, N> pow(lint p) const { FixedSquareMatrix<T, N> res, memo = *this; rep(i, N) res[i][i] = 1; while (p) { if (p & 1) res *= memo; p >>= 1; memo *= memo; } return res; } constexpr T determinant() const { FixedSquareMatrix<T, N> tmp = *this; T res(1); rep(i, N) { if (tmp[i][i] == 0) { for (int j = i + 1; j < N; j++) { if (tmp[j][i]) { std::swap(tmp[i], tmp[j]); res = -res; break; } } } res *= tmp[i][i]; for (int j = i + 1; j < N; j++) { T inv = T(1) / tmp[i][i]; for (int k = i + 1; k < N; k++) { tmp[j][k] -= tmp[j][i] * inv * tmp[i][k]; } } } return res; } constexpr static FixedSquareMatrix<T, N> ident() { FixedSquareMatrix<T, N> res; rep(i, N) res[i][i] = 1; return res; } }; /** * @title Matrix */ #line 5 "test/yosupo/matrix_product.test.cpp" using ModInt = StaticModInt<998244353>; int N, M, K; int main() { scanf("%d%d%d", &N, &M, &K); Matrix<ModInt> mat1(N, M), mat2(M, K); rep(i, N) rep(j, M) std::cin >> mat1[i][j]; rep(i, M) rep(j, K) std::cin >> mat2[i][j]; auto res = mat1 * mat2; rep(i, N) std::cout << res[i] << std::endl; return 0; }