#include #ifdef LOCAL #include "debugger.hpp" #else #define dbg(...) #endif using i64 = long long; template constexpr T power(T a, i64 b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; } constexpr i64 mul(i64 a, i64 b, i64 p) { i64 res = a * b - i64(1.L * a * b / p) * p; res %= p; if (res < 0) { res += p; } return res; } template struct MLong { i64 x; constexpr MLong() : x{} {} constexpr MLong(i64 x) : x{norm(x % getMod())} {} static i64 Mod; constexpr static i64 getMod() { if (P > 0) { return P; } else { return Mod; } } constexpr static int getRoot() { if (getMod() == 1231453023109121) return 3; assert(false); } constexpr static void setMod(i64 Mod_) { Mod = Mod_; } constexpr i64 norm(i64 x) const { if (x < 0) { x += getMod(); } if (x >= getMod()) { x -= getMod(); } return x; } constexpr i64 val() const { return x; } explicit constexpr operator i64() const { return x; } explicit constexpr operator bool() const { return x != 0;} constexpr MLong operator-() const { MLong res; res.x = norm(getMod() - x); return res; } constexpr MLong inv() const { i64 a = getMod(), b = x; i64 y = 0, z = 1; for (; b; ) { i64 k = a / b; std::swap(a -= k * b, b); std::swap(y -= k * z, z); } assert(a == 1); return MLong(y); } constexpr MLong &operator*=(MLong rhs) & { x = mul(x, rhs.x, getMod()); return *this; } constexpr MLong &operator+=(MLong rhs) & { x = norm(x + rhs.x); return *this; } constexpr MLong &operator-=(MLong rhs) & { x = norm(x - rhs.x); return *this; } constexpr MLong &operator/=(MLong rhs) & { return *this *= rhs.inv(); } friend constexpr MLong operator*(MLong lhs, MLong rhs) { MLong res = lhs; res *= rhs; return res; } friend constexpr MLong operator+(MLong lhs, MLong rhs) { MLong res = lhs; res += rhs; return res; } friend constexpr MLong operator-(MLong lhs, MLong rhs) { MLong res = lhs; res -= rhs; return res; } friend constexpr MLong operator/(MLong lhs, MLong rhs) { MLong res = lhs; res /= rhs; return res; } friend constexpr std::istream &operator>>(std::istream &is, MLong &a) { i64 v; is >> v; a = MLong(v); return is; } friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) { return os << a.val(); } friend constexpr bool operator==(MLong lhs, MLong rhs) { return lhs.val() == rhs.val(); } friend constexpr bool operator!=(MLong lhs, MLong rhs) { return lhs.val() != rhs.val(); } }; template<> i64 MLong<0LL>::Mod = i64(1E18) + 9; template struct MInt { int x; constexpr MInt() : x{} {} constexpr MInt(i64 x) : x{norm(x % getMod())} {} static int Mod; constexpr static int getMod() { if (P > 0) { return P; } else { return Mod; } } constexpr static int getRoot() { if (getMod() == 998244353) return 3; assert(false); } constexpr static void setMod(int Mod_) { Mod = Mod_; } constexpr int norm(int x) const { if (x < 0) { x += getMod(); } if (x >= getMod()) { x -= getMod(); } return x; } constexpr int val() const { return x; } explicit operator MLong

() const { return MLong

(x); } explicit constexpr operator int() const { return x; } explicit constexpr operator bool() const { return x != 0;} constexpr MInt operator-() const { MInt res; res.x = norm(getMod() - x); return res; } constexpr MInt inv() const { unsigned a = getMod(), b = x; int y = 0, z = 1; for (; b; ) { int k = a / b; std::swap(a -= k * b, b); std::swap(y -= k * z, z); } assert(a == 1U); return MInt(y); } constexpr MInt &operator*=(MInt rhs) & { x = 1LL * x * rhs.x % getMod(); return *this; } constexpr MInt &operator+=(MInt rhs) & { x = norm(x + rhs.x); return *this; } constexpr MInt &operator-=(MInt rhs) & { x = norm(x - rhs.x); return *this; } constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); } friend constexpr MInt operator*(MInt lhs, MInt rhs) { MInt res = lhs; res *= rhs; return res; } friend constexpr MInt operator+(MInt lhs, MInt rhs) { MInt res = lhs; res += rhs; return res; } friend constexpr MInt operator-(MInt lhs, MInt rhs) { MInt res = lhs; res -= rhs; return res; } friend constexpr MInt operator/(MInt lhs, MInt rhs) { MInt res = lhs; res /= rhs; return res; } friend constexpr std::istream &operator>>(std::istream &is, MInt &a) { i64 v; is >> v; a = MInt(v); return is; } friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) { return os << a.val(); } friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); } friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); } }; template<> int MInt<0>::Mod = 998244353; template constexpr MInt

CInv = MInt

(V).inv(); constexpr int P = 998244353; // using Z = MInt

; #include "atcoder/all" using Z = atcoder::modint998244353; template T count_minor(const std::vector>& matrix, int idx = 0, int idy = 0) { assert(matrix.size() == matrix[0].size()); int n = matrix.size(); assert(idx < n && idy < n); if (n == 1) { return 0; } std::vector minor(n-1, std::vector(n-1)); for (int i = 0; i < n; ++i) { if (i == idx) continue; for (int j = 0; j < n; ++j) { if (j == idy) continue; minor[i - (i > idx)][j - (j > idy)] = matrix[i][j]; } } n--; auto gauss=[&]()->T { for (int i = 0; i < n; ++i) { if (minor[i][i] == 0) { for (int j = i + 1; j < n; ++j) { if (minor[j][i] != T{}) { // for (int k = 0; k < n; ++k) { // std::swap(minor[i][k], minor[j][k]); // } std::swap(minor[i], minor[j]); break; } } } if (minor[i][i] == 0) { return 0; } for (int j = i + 1; j < n; ++j) { if (i == j) continue; T mul = minor[j][i] / minor[i][i]; for (int k = i; k < n; ++k) { minor[j][k] -= mul * minor[i][k]; } } } T res = 1; for (int i = 0; i < n; ++i) { res *= minor[i][i]; } return res; }; return gauss(); } // Kirchhoff Z Kirchhoff(const std::vector> &G) { int n = G.size(); std::vector> L(n, std::vector(n)); for (int i = 0; i < n; ++i) { L[i][i] = G[i].size(); for (auto &j : G[i]) { L[i][j]--; } } return count_minor(L); } /// @param A square matrix of size n /// @return characteristic polynomial of A, which is `det(xI - M)` template std::vector char_poly(std::vector> M) { int N = M.size(); assert(N == M[0].size()); // Hessenberg Reduction for (int i = 0; i < N - 2; i++) { int p = -1; for (int j = i + 1; j < N; j++) { if (M[j][i] != T(0)) { p = j; break; } } if (p == -1) { continue; } M[i + 1].swap(M[p]); for (int j = 0; j < N; j++) { std::swap(M[j][i + 1], M[j][p]); } T r = T(1) / M[i + 1][i]; for (int j = i + 2; j < N; j++) { T c = M[j][i] * r; for (int k = 0; k < N; k++) M[j][k] -= M[i + 1][k] * c; for (int k = 0; k < N; k++) M[k][i + 1] += M[k][j] * c; } } // La Budde's Method std::vector> P = {{T(1)}}; for (int i = 0; i < N; i++) { std::vector f(i + 2, 0); for (int j = 0; j <= i; j++) f[j + 1] += P[i][j]; for (int j = 0; j <= i; j++) f[j] -= P[i][j] * M[i][i]; T b = 1; for (int j = i - 1; j >= 0; j--) { b *= M[j + 1][j]; T h = -M[j][i] * b; for (int k = 0; k <= j; k++) f[k] += h * P[j][k]; } P.push_back(f); } return P.back(); } /// @brief calculate `det(Ax + B)`, where A and B are square matrices of size n /// @tparam T usually Z /// @tparam Matrix usually std::vector>, or custom matrix class /// @param A /// @param B /// @return `det(Ax + B)` template std::vector det_linear(std::vector> A, std::vector> B) { int N = A.size(), nu = 0; T det = 1; for (int i = 0; i < N; i++) { // do normal gaussian elimination int p = -1; for (int j = i; j < N; j++) { if (A[j][i] != T(0)) { p = j; break; } } // replace B with A if (p == -1) { // Increase nullity by 1 if (++nu > N) { return std::vector(N + 1, 0); } // i-th column is empty for (int j = 0; j < i; j++) { for (int k = 0; k < N; k++) { B[k][i] -= B[k][j] * A[j][i]; } A[j][i] = 0; } for (int j = 0; j < N; j++) { std::swap(A[j][i], B[j][i]); } // retry --i; continue; } if (p != i) { A[i].swap(A[p]); B[i].swap(B[p]); det = -det; } det *= A[i][i]; T c = T(1) / A[i][i]; for (int j = 0; j < N; j++) { A[i][j] *= c, B[i][j] *= c; } for (int j = 0; j < N; j++) { if (j != i) { T c = A[j][i]; for (int k = 0; k < N; k++) { A[j][k] -= A[i][k] * c, B[j][k] -= B[i][k] * c; } } } } for (auto &y : B) { for (T &x : y) { x = -x; } } auto f = char_poly(B); for (T &x : f) { x *= det; } f.erase(f.begin(), f.begin() + nu); f.resize(N + 1); return f; } void solv() { int n; std::cin >> n; std::vector> D1(n, std::vector(n)); auto D2 = D1; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { int x; std::cin >> x; D2[i][j] = x; } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { int x; std::cin >> x; D1[i][j] = x; } } auto poly = det_linear(D1, D2); for (int i = 0; i <= n; ++i) { if (i >= poly.size()) { std::cout << "0\n"; } else { std::cout << poly[i].val() << '\n'; } } } signed main() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr); int tt = 1; // std::cin >> tt; while (tt--) { solv(); } return 0; }