QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#150358#59. Determinant of A+BzNOI_AK_ME0 110ms6860kbC++233.7kb2023-08-25 16:35:192024-03-04 04:46:22

Judging History

你现在查看的是最新测评结果

  • [2024-05-05 11:54:08]
  • hack成功,自动添加数据
  • (/hack/617)
  • [2024-05-05 11:38:15]
  • hack成功,自动添加数据
  • (/hack/616)
  • [2024-03-04 04:46:22]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:110ms
  • 内存:6860kb
  • [2024-03-04 04:35:40]
  • hack成功,自动添加数据
  • (/hack/552)
  • [2023-08-25 16:35:23]
  • 评测
  • 测评结果:0
  • 用时:106ms
  • 内存:6792kb
  • [2023-08-25 16:35:19]
  • 提交

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%