#include #include using namespace std; using mint = atcoder::modint998244353; using vec = vector; using mat = vector; vec characteristic_polynomial(mat A) { int n = A.size(); for (int j = 0; j < n - 2; j++) { for (int i = j + 2; i < n; i++) { if (A[i][j] != 0) { swap(A[j + 1], A[i]); for (int k = 0; k < n; k++) { swap(A[k][j + 1], A[k][i]); } break; } } if (A[j + 1][j] != 0) { mint ajj_inv = A[j + 1][j].inv(); for (int i = j + 2; i < n; i++) { mint c = A[i][j] * ajj_inv; for (int k = j; k < n; k++) { A[i][k] -= A[j + 1][k] * c; } for (int k = 0; k < n; k++) { A[k][j + 1] += A[k][i] * c; } } } } mat p(n + 1); p[0] = {1}; for (int i = 0; i < n; i++) { p[i + 1].resize(i + 2, 0); for (int j = 0; j <= i; j++) { p[i + 1][j + 1] += p[i][j]; p[i + 1][j] -= p[i][j] * A[i][i]; } mint c = 1; for (int k = 1; k <= i; k++) { c *= -A[i + 1 - k][i - k]; mint x = c * A[i - k][i]; if (k % 2 == 0) { x *= -1; } for (int j = 0; j <= i - k; j++) { p[i + 1][j] += p[i - k][j] * x; } } } return p[n]; } vec fact(1000, 1); vec shift(vec f, mint a) { int n = f.size(); vec a_pow(n, 1); for (int i = 1; i < n; i++) { a_pow[i] = a_pow[i - 1] * a; } vec ret(n); for (int i = 0; i < n; i++) { for (int k = 0; k <= i; k++) { ret[k] += fact[i] / (fact[i - k] * fact[k]) * f[i] * a_pow[i - k]; } } return ret; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); for (int i = 2; i < 1000; i++) { fact[i] = fact[i - 1] * i; } int n; cin >> n; mat m0(n, vec(n)), m1(n, vec(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int mij; cin >> mij; m0[i][j] = mij; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int mij; cin >> mij; m1[i][j] = mij; } } random_device seed_gen; mt19937 engine(seed_gen()); uniform_int_distribution<> dist_998(0, 998244352); mint sh = dist_998(engine); // convert x to x - sh for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { m0[i][j] -= sh * m1[i][j]; } } // convert m0 to identity mint detab = 1; for (int i = 0; i < n; i++) { int j0 = i; while (j0 < n && m0[j0][i] == 0) { j0++; } if (j0 == n) { for (int j = 0; j <= n; j++) { cout << 0 << "\n"; } return 0; } if (i != j0) { swap(m0[i], m0[j0]); swap(m1[i], m1[j0]); detab *= -1; } mint mii_inv = m0[i][i].inv(); detab *= mii_inv; for (int j = 0; j < n; j++) { m0[i][j] *= mii_inv; m1[i][j] *= mii_inv; } for (int j = i + 1; j < n; j++) { // m_j -= m0[j][i] * mi; mint mji = m0[j][i]; for (int k = 0; k < n; k++) { m0[j][k] -= mji * m0[i][k]; m1[j][k] -= mji * m1[i][k]; } } } for (int j = 1; j < n; j++) { for (int i = 0; i < j; i++) { // m_i -= m0[i][j] * m_j mint mij = m0[i][j]; for (int k = 0; k < n; k++) { m0[i][k] -= mij * m0[j][k]; m1[i][k] -= mij * m1[j][k]; } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { m1[i][j] *= -1; } } vec ans = characteristic_polynomial(m1); mint detab_inv = detab.inv(); for (int i = 0; i <= n; i++) { ans[i] *= detab_inv; } reverse(ans.begin(), ans.end()); ans = shift(ans, sh); for (int i = 0; i <= n; i++) { cout << ans[i].val() << "\n"; } }