QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#150351#59. Determinant of A+BzNOI_AK_MECompile Error//C++233.7kb2023-08-25 16:33:292023-08-25 16:33:31

Judging History

你现在查看的是测评时间为 2023-08-25 16:33:31 的历史记录

  • [2024-05-05 11:54:08]
  • hack成功,自动添加数据
  • (/hack/617)
  • [2024-05-05 11:38:15]
  • hack成功,自动添加数据
  • (/hack/616)
  • [2024-03-04 04:46:16]
  • 管理员手动重测本题所有提交记录
  • [2024-03-04 04:35:40]
  • hack成功,自动添加数据
  • (/hack/552)
  • [2023-08-25 16:33:31]
  • 评测
  • [2023-08-25 16:33:29]
  • 提交

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
#define qmp(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;
}
void gauss() {
    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]);
}
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]);

    gauss();

    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("");
}

详细

answer.code: In function ‘void gauss()’:
answer.code:45:49: error: ‘qmo’ was not declared in this scope; did you mean ‘qmp’?
   45 |                 swapc(a, i, j), swapc(b, i, j), qmo(mul = -mul);
      |                                                 ^~~
      |                                                 qmp
answer.code:78:13: error: ‘qmo’ was not declared in this scope; did you mean ‘qmp’?
   78 |             qmo(a[i][j] = -a[i][j]);
      |             ^~~
      |             qmp
answer.code: In function ‘int main()’:
answer.code:115:21: error: ‘qmo’ was not declared in this scope; did you mean ‘qmp’?
  115 |                     qmo(a[j][k] -= 1ll * t * a[i + 1][k] % mod);
      |                     ^~~
      |                     qmp
answer.code:129:13: error: ‘qmo’ was not declared in this scope; did you mean ‘qmp’?
  129 |             qmo(p[k][i] -= 1ll * a[k][k] * p[k - 1][i] % mod);
      |             ^~~
      |             qmp
answer.code:143:18: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=]
  143 |         printf("%d ", 1ll * mul * p[n][min(n + 1, i + ty)] % mod);
      |                 ~^
      |                  |
      |                  int
      |                 %lld
answer.code:81:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   81 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
answer.code:85:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   85 |             scanf("%d", &a[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~
answer.code:89:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   89 |             scanf("%d", &b[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~