QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#150358 | #59. Determinant of A+Bz | NOI_AK_ME | 0 | 110ms | 6860kb | C++23 | 3.7kb | 2023-08-25 16:35:19 | 2024-03-04 04:46:22 |
Judging History
answer
#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
int n, m, K, mul, ty;
int a[510][510], b[510][510], p[510][510];
char s[1000010];
#define swap(a, b) a ^= b ^= a ^= b
inline void qmo(int &x) {
x += (x >> 31) & mod;
}
int ksm(int a, int k) {
int res = 1;
for (; k; k >>= 1, a = 1ll * a * a % mod)
if (k & 1)
res = 1ll * res * a % mod;
return res;
}
void swapr(int a[][510], int x, int y) {
for (int k = 1; k <= n; k++)
swap(a[x][k], a[y][k]);
}
void addr(int a[][510], int x, int y, int z) {
for (int k = 1; k <= n; k++)
a[y][k] = (a[y][k] + 1ll * a[x][k] * z) % mod;
}
void swapc(int a[][510], int x, int y) {
for (int k = 1; k <= n; k++)
swap(a[k][x], a[k][y]);
}
void addc(int a[][510], int x, int y, int z) {
for (int k = 1; k <= n; k++)
a[k][y] = (a[k][y] + 1ll * a[k][x] * z) % mod;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &b[i][j]);
mul = 1, ty = 0;
for (int i = 1; i <= n; i++) {
while (!b[i][i]) {
int j = i;
while (!b[i][j] && j <= n)
j++;
if (j <= n) {
swapc(a, i, j), swapc(b, i, j), qmo(mul = -mul);
break;
}
ty++;
if (ty > n)
break;
for (int j = 1; j <= n; j++)
b[i][j] = a[i][j], a[i][j] = 0;
for (int j = 1; j < i; j++)
if (b[i][j])
addr(a, j, i, mod - b[i][j]), addr(b, j, i, mod - b[i][j]);
}
if (ty > n)
break;
int inv = ksm(b[i][i], mod - 2);
mul = 1ll * mul * b[i][i] % mod;
for (int j = 1; j <= n; j++)
a[i][j] = 1ll * a[i][j] * inv % mod, b[i][j] = 1ll * b[i][j] * inv % mod;
for (int j = 1; j <= n; j++)
if ((i ^ j) && b[j][i])
addr(a, i, j, mod - b[j][i]), addr(b, i, j, mod - b[j][i]);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
qmo(a[i][j] = -a[i][j]);
for (int i = 1; i < n; i++) {
int j = i + 1;
while (!a[j][i] && j <= n)
j++;
if (j > n)
continue;
for (int k = 1; k <= n; k++)
swap(a[i + 1][k], a[j][k]);
for (int k = 1; k <= n; k++)
swap(a[k][i + 1], a[k][j]);
int inv = ksm(a[i + 1][i], mod - 2);
for (int j = i + 2; j <= n; j++)
if (a[j][i]) {
int t = 1ll * inv * a[j][i] % mod;
for (int k = i; k <= n; k++)
qmo(a[j][k] -= 1ll * t * a[i + 1][k] % mod);
for (int k = 1; k <= n; k++)
a[k][i + 1] = (a[k][i + 1] + 1ll * t * a[k][j]) % mod;
}
}
p[0][0] = 1;
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= k; i++)
p[k][i] = p[k - 1][i - 1];
for (int i = 0; i <= k; i++)
qmo(p[k][i] -= 1ll * a[k][k] * p[k - 1][i] % mod);
int nw = 1, tp;
for (int i = k - 1; i; i--) {
nw = 1ll * nw * a[i + 1][i] % mod;
tp = 1ll * (mod - nw) * a[i][k] % mod;
for (int j = 0; j <= i; j++)
p[k][j] = (p[k][j] + 1ll * tp * p[i - 1][j]) % mod;
}
}
for (int i = 0; i <= n; i++)
printf("%d ", 1ll * mul * p[n][min(n + 1, i + ty)] % mod);
puts("");
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 6036kb
input:
50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 179093706 0 0 0 0 0 873235003 0 873022990 0 0 0 0 150372208 0 0 0 0 0 0 0 0 540031202 441544333 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30490606 0 23238599 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 978496851 37424765 195556028 638514938 499634042 552457111 311512896 75148877 373437501 144803461 59187019 129331670 121153985 113793663 255782475 193325562 309242418 71513851 637564235 482107825 447272184 887198983 419788284 805771870 536494034
result:
wrong answer 2nd numbers differ - expected: '436083536', found: '0'
Subtask #2:
score: 0
Wrong Answer
Test #51:
score: 0
Wrong Answer
time: 110ms
memory: 6860kb
input:
500 0 0 0 0 0 482890969 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1077401 0 0 210804413 0 508044994 0 0 0 398405351 0 0 0 0 0 0 0 171917316 0 0 0 0 0 0 0 0 0 0 0 429230725 0 0 0 0 0 45665526 0 0 0 925078893 0 0 396149045 0 0 0 595858405 0 0 0 0 0 57208...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '197564738', found: '0'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%