QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#552 | #313942 | #59. Determinant of A+Bz | Qingyu | alpha1022 | Success! | 2024-03-04 04:35:27 | 2024-03-04 04:35:27 |
詳細信息
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'
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#313942 | #59. Determinant of A+Bz | alpha1022 | 97 | 443ms | 11100kb | C++14 | 5.3kb | 2024-01-25 10:35:08 | 2024-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]);
}