#pragma GCC optimize(3) #pragma GCC target("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #pragma GCC optimize(2) #include using namespace std; using LL = long long; const int kMaxN = 405, kM = 998244353; LL a[kMaxN][kMaxN], b[kMaxN][kMaxN], f[kMaxN][kMaxN], n, val = 1, cnt; LL P(LL x, LL y) { LL ans = 1; for (LL i = 1; i <= y; i <<= 1, x = x * x % kM) { (y & i) && (ans = ans * x % kM); } return ans; } void Init() { // ???????? for (int i = 1; i <= n; i++) { // ?? i ?? i+1 ??? 1 int pos = 0; for (int j = i + 1; j <= n; j++) { if (a[j][i]) { pos = j; break; } } if (!pos) { continue; } swap(a[i + 1], a[pos]); for (int k = 1; k <= n; k++) { swap(a[k][i + 1], a[k][pos]); } LL f = a[i + 1][i], inv = P(f, kM - 2); for (int j = i; j <= n; j++) { a[i + 1][j] = a[i + 1][j] * inv % kM; } for (int j = 1; j <= n; j++) { a[j][i + 1] = a[j][i + 1] * f % kM; } for (int j = i + 2; j <= n; j++) { LL val = a[j][i]; for (int k = 1; k <= n; k++) { a[k][i + 1] = (a[k][i + 1] + a[k][j] * val) % kM; } val = (kM - val) % kM; for (int k = i; k <= n; k++) { a[j][k] = (a[j][k] + a[i + 1][k] * val) % kM; } } } } void Dp() { f[0][0] = 1; for (int i = 1; i <= n; i++) { LL val = kM - 1; for (int j = i; j >= 1; j--) { LL g = val * a[j][i] % kM; for (int k = 0; k < j; k++) { f[i][k] = (f[i][k] + g * f[j - 1][k]) % kM; } val = val * a[j][j - 1] % kM; } for (int k = 1; k <= i; k++) { f[i][k] = (f[i - 1][k - 1] + f[i][k]) % kM; } } } void Work(int x) { // ?(x,x)???0 for (int i = 1; i < x; i++) { // ?x??i? // ?? i ????????? for (int j = 1; j <= n; j++) { a[j][x] = (a[j][x] - a[j][i] * b[i][x]) % kM; } b[i][x] = 0; } for (int i = 1; i <= n; i++) { b[i][x] = a[i][x], a[i][x] = 0; } } void Debug() { cout << "a:\n"; for (int x = 1; x <= n; x++) { for (int y = 1; y <= n; y++) { cout << a[x][y] << " "; } cout << "\n"; } cout << "b:\n"; for (int x = 1; x <= n; x++) { for (int y = 1; y <= n; y++) { cout << b[x][y] << " "; } cout << "\n"; } } void Calc() { // ???????? for (int i = 1; i <= n; i++) { int p = 0; for (int j = i; j <= n; j++) { if (b[j][i]) { p = j; break; } } if (!p) { cnt++; Work(i), i--; } else { if (p != i) { swap(b[i], b[p]), swap(a[i], a[p]); val = (kM - val) % kM; } val = val * b[i][i] % kM; LL v = P(b[i][i], kM - 2); for (int j = n; j >= 1; j--) { a[i][j] = a[i][j] * v % kM; b[i][j] = b[i][j] * v % kM; } for (int j = 1; j <= n; j++) { if (i != j) { LL x = b[j][i]; for (int k = n; k >= 1; k--) { a[j][k] = (a[j][k] - x * a[i][k]) % kM; b[j][k] = (b[j][k] - x * b[i][k]) % kM; } } } // Debug(); } } // ??????? for (int i = n; i >= 1; i--) { // ?i? for (int j = i + 1; j <= n; j++) { // ???j? LL val = b[i][j]; for (int k = 1; k <= n; k++) { b[i][k] = (b[i][k] - b[j][k] * val) % kM; a[i][k] = (a[i][k] - a[j][k] * val) % kM; } } } // Debug(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { a[i][j] = (a[i][j] + kM) % kM; a[i][j] = (kM - a[i][j]) % kM; } } } int main() { ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> a[i][j]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> b[i][j]; } } // cout << "\n\n\n\n\n\n"; Calc(); Init(); Dp(); val = (val % kM + kM) % kM; for (int i = 0; i <= n - cnt; i++) { cout << f[n][i + cnt] * val % kM << "\n"; } for (int i = 1; i <= cnt; i++) { cout << 0 << "\n"; } return 0; }