QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#552#313942#59. Determinant of A+BzQingyualpha1022Success!2024-03-04 04:35:272024-03-04 04:35:27

Details

Extra Test:

Wrong Answer
time: 0ms
memory: 7980kb

input:

2
1 1
1 0
0 0
1 1

output:

0 0 0

result:

wrong answer 1st numbers differ - expected: '998244352', found: '0'

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#313942#59. Determinant of A+Bzalpha102297 443ms11100kbC++145.3kb2024-01-25 10:35:082024-03-04 04:46:54

answer

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
const int mod = 998244353;
int norm(int x) { return x >= mod ? x - mod : x; }
int reduce(int x) { return x < 0 ? x + mod : x; }
int neg(int x) { return x ? mod - x : 0; }
void add(int &x, int y) { if ((x += y - mod) < 0) x += mod; }
void sub(int &x, int y) { if ((x -= y) < 0) x += mod; }
int mpow(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1) {
    if (b & 1) ret = (ll)ret * a % mod;
    a = (ll)a * a % mod;
  }
  return ret;
}

namespace Matrix {
 
  const int D = 1;
  const int N = 500;
 
  template<class T>
  vector<int> charPoly(int n, T mat) {
    static int a[N + 5][N + 5], poly[N + 5][N + 5];
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) a[i][j] = neg(mat[i][j]);
    for (int i = 1; i < n; ++i) {
      int pivot = i + 1;
      for (; pivot <= n && !a[pivot][i]; ++pivot);
      if (pivot > n) continue;
      if (pivot > i + 1) {
        for (int j = i; j <= n; ++j) swap(a[i + 1][j], a[pivot][j]);
        for (int j = 1; j <= n; ++j) swap(a[j][i + 1], a[j][pivot]);
      }
      int nv = mpow(a[i + 1][i], mod - 2);
      for (int j = i + 2; j <= n; ++j)
        if (a[j][i]) {
          int t = (ll)a[j][i] * nv % mod;
          for (int k = i; k <= n; ++k) a[j][k] = (a[j][k] + (ll)(mod - t) * a[i + 1][k]) % mod;
          for (int k = 1; k <= n; ++k) a[k][i + 1] = (a[k][i + 1] + (ll)t * a[k][j]) % mod;
        }
    }
    poly[n + 1][0] = 1;
    for (int i = n; i; --i) {
      poly[i][0] = 0;
      for (int j = 1; j <= n + 1 - i; ++j) poly[i][j] = poly[i + 1][j - 1];
      for (int j = i, t = 1; j <= n && t; t = (ll)t * a[j + 1][j] % mod, ++j) {
        int coe = (ll)t * a[i][j] % mod;
        if (!coe) continue;
        if ((i ^ j) & 1) coe = mod - coe;
        for (int k = 0; k <= n - j; ++k) poly[i][k] = (poly[i][k] + (ll)poly[j + 1][k] * coe) % mod;
      }
    }
    return vector<int>(poly[1], poly[1] + n + 1);
  }
 
  template<class T>
  int det(int n, T mat) {
    static int a[N + 5][N + 5];
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) a[i][j] = mat[i][j];
    int ret = 1;
    for (int i = 1; i <= n; ++i) {
      int pivot = i;
      for (; pivot <= n && !a[pivot][i]; ++pivot);
      if (pivot > n) return 0;
      if (pivot > i) {
        ret = mod - ret;
        for (int j = i; j <= n; ++j) swap(a[i][j], a[pivot][j]);
      }
      int nv = mpow(a[i][i], mod - 2);
      for (int j = i + 1; j <= n; ++j)
        if (a[j][i]) {
          int t = (ll)a[j][i] * nv % mod;
          for (int k = i; k <= n; ++k) a[j][k] = (a[j][k] + (ll)(mod - t) * a[i][k]) % mod;
        }
    }
    for (int i = 1; i <= n; ++i) ret = (ll)ret * a[i][i] % mod;
    return ret;
  }

  template<class T>
  vector<int> detPoly(int n, int d, T mat) {
    static int a[D + 1][N + 5][N + 5], b[N + 5][N + 5];
    for (int e = 0; e <= d; ++e)
      for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) a[e][i][j] = mat[e][i][j];
    int offset = 0, coe = 1;
    for (int i = 1; i <= n; ++i) {
      int pivot = n + 1;
      for (int rep = 0; ; ++rep) {
        for (int j = 1; j < i; ++j)
          if (a[d][j][i]) {
            int t = mod - a[d][j][i];
            for (int e = 0; e <= d; ++e)
              for (int k = 1; k <= n; ++k)
                if (a[e][k][j])
                  a[e][k][i] = (a[e][k][i] + (ll)a[e][k][j] * t) % mod;
          }
        for (pivot = i; pivot <= n && !a[d][pivot][i]; ++pivot);
        if (pivot <= n || rep == d) break;
        ++offset;
        for (int e = d; e; --e)
          for (int j = 1; j <= n; ++j) a[e][j][i] = a[e - 1][j][i];
        for (int j = 1; j <= n; ++j) a[0][j][i] = 0;
      }
      if (pivot > n) return vector<int>(n * d + 1, 0);
      if (pivot > i) {
        coe = mod - coe;
        for (int e = 0; e <= d; ++e)
          for (int j = 1; j <= n; ++j) swap(a[e][i][j], a[e][pivot][j]);
      }
      int nv = mpow(a[d][i][i], mod - 2); coe = (ll)coe * a[d][i][i] % mod;
      for (int e = 0; e <= d; ++e)
        for (int j = 1; j <= n; ++j)
          if (a[e][i][j]) a[e][i][j] = (ll)a[e][i][j] * nv % mod;
      for (int j = i + 1; j <= n; ++j)
        if (a[d][j][i]) {
          int t = mod - a[d][j][i];
          for (int e = 0; e <= d; ++e)
            for (int k = 1; k <= n; ++k)
              if (a[e][i][k]) a[e][j][k] = (a[e][j][k] + (ll)a[e][i][k] * t) % mod;
        }
    }
    for (int i = 1; i <= n * (d - 1); ++i) b[i][n + i] = 1;
    for (int e = 0; e < d; ++e)
      for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
          b[n * (d - 1) + i][n * e + j] = neg(a[e][i][j]);
    auto res = charPoly(n * d, b);
    vector<int> ret(n * d - offset + 1);
    for (int i = 0; i < ret.size(); ++i) ret[i] = (ll)coe * res[i + offset] % mod;
    ret.resize(n * d + 1);
    return ret;
  }
 
}

using Matrix::detPoly;

const int N = 500;

int n;
int a[2][N + 5][N + 5];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      scanf("%d", a[0][i] + j);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      scanf("%d", a[1][i] + j);
  auto ans = detPoly(n, 1, a);
  for (int i = 0; i <= n; ++i) printf("%d%c", ans[i], " \n"[i == n]);
}