QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#566018#8473. Matrices and Determinantsucup-team1231#AC ✓13ms3944kbC++202.7kb2024-09-15 22:53:522024-09-15 22:53:53

Judging History

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

  • [2024-09-15 22:53:53]
  • 评测
  • 测评结果:AC
  • 用时:13ms
  • 内存:3944kb
  • [2024-09-15 22:53:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
LL A[5][5], L[5][5], R[5][5];
void rswap(int i, int j) {
    for(int k = 0; k < n; k++) {
        swap(A[i][k], A[j][k]); swap(L[k][i], L[k][j]);
    }
    for(int k = 0; k < n; k++) {
        A[i][k] *= -1; L[k][i] *= -1;
    }
}
void cswap(int i, int j) {
    for(int k = 0; k < n; k++) {
        swap(A[k][i], A[k][j]); swap(R[i][k], R[j][k]);
    }
    for(int k = 0; k < n; k++) {
        A[k][i] *= -1; R[i][k] *= -1;
    }
}
void raddmul(int i, int j, LL t) {
    for(int k = 0; k < n; k++) {
        A[i][k] += A[j][k] * t;
        L[k][j] -= L[k][i] * t;
    }
}
void caddmul(int i, int j, LL t) {
    for(int k = 0; k < n; k++) {
        A[k][i] += A[k][j] * t;
        R[j][k] -= R[i][k] * t;
    }
}

void rreduce(int i, int j) {
    if(A[i][i] != 0 && A[j][i] % A[i][i] == 0) {
        raddmul(j, i, -A[j][i] / A[i][i]);
        return;
    }
    while(A[j][i] != 0) {
        raddmul(i, j, -A[i][i] / A[j][i]);
        rswap(i, j);
    }
}
void creduce(int i, int j) {
    if(A[i][i] != 0 && A[i][j] % A[i][i] == 0) {
        caddmul(j, i, -A[i][j] / A[i][i]);
        return;
    }
    while(A[i][j] != 0) {
        caddmul(i, j, -A[i][i] / A[i][j]);
        cswap(i, j);
    }
}

void reduce(int m) {
    bool ok;
    do {
        for(int i = 0; i < m - 1; i++) rreduce(m - 1, i);
        for(int i = 0; i < m - 1; i++) creduce(m - 1, i);
        ok = true;
        for(int i = 0; i < m - 1; i++) if(A[m - 1][i] != 0 || A[i][m - 1] != 0) ok = false;
    } while(!ok);
}

int X[5], Y[5];
void solve() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) {
            scanf("%lld", &A[i][j]);
            L[i][j] = R[i][j] = i == j;
        }
    
    for(int i = n; i >= 1; i--) reduce(i);

    LL prod = 1;
    for(int i = 0; i < n; i++) prod *= A[i][i];
    if(prod <= 0) {
        printf("No\n"); return;
    }
    LL ss = sqrt(prod + 0.5);
    if(ss * ss != prod) {
        printf("No\n"); return;
    }
    for(int i = 0; i < n; i++) {
        LL g = __gcd(ss, A[i][i]);
        X[i] = g;
        Y[i] = A[i][i] / g;
        ss /= g;
    }

    printf("Yes\n");
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++)
            printf("%lld ", L[i][j] * X[j]), assert(L[i][j] * X[j] <= 1e18);
        printf("\n");
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++)
            printf("%lld ", R[i][j] * Y[i]), assert(R[i][j] * Y[i] <= 1e18);
        printf("\n");
    }
}
int main() {
    int T;
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3888kb

input:

3
2
2 0
0 2
2
2 1
1 2
1
1

output:

Yes
2 0 
0 1 
1 0 
0 2 
No
Yes
1 
1 

result:

ok OK, Accepted. (3 test cases)

Test #2:

score: 0
Accepted
time: 13ms
memory: 3824kb

input:

10000
3
10 0 1
0 0 4
2 10 0
3
2 -2 5
-6 9 0
2 1 10
4
-7 0 7 7
0 0 -10 0
0 0 -10 -10
8 -7 3 9
3
-3 3 3
5 -7 -9
-8 -6 -2
4
9 -8 4 -3
-3 -4 0 0
0 7 0 0
10 -4 7 0
4
3 -10 1 -3
5 5 -3 9
0 -5 -5 -10
3 0 4 -8
3
10 9 0
0 10 0
-5 -1 4
1
-10
4
0 7 0 0
0 -2 7 0
1 -2 7 5
5 -10 -1 0
4
3 1 4 0
-2 3 2 -4
-1 2 -10 ...

output:

No
No
Yes
630 -105 -63 7 
0 2 -5 0 
-910 152 90 -10 
840 -140 -84 9 
14 7 0 0 
65 35 0 0 
26 14 2 0 
-52 21 19 1 
No
No
No
Yes
0 -1 10 
20 10 0 
0 0 -1 
-20 0 20 
40 1 -40 
5 1 -4 
No
No
No
Yes
-9 9 0 
18 -19 -3 
18 -19 -2 
9 0 0 
9 1 0 
-3 -8 1 
No
Yes
10 15 0 
0 -1 -3 
0 2 5 
70 15 0 
-47 -10 0 
1...

result:

ok OK, Accepted. (10000 test cases)

Test #3:

score: 0
Accepted
time: 13ms
memory: 3860kb

input:

10000
3
0 -3 5
5 0 0
2 1 0
4
2 0 -2 0
-7 4 6 4
-2 8 -3 -10
3 -8 3 -7
4
-7 -4 5 2
5 0 0 4
0 0 0 7
-8 7 0 1
2
4 6
-8 -6
4
0 7 2 -3
0 0 0 -9
0 0 -9 0
7 8 9 2
4
-7 8 -10 -8
6 8 -1 6
8 -10 -7 3
2 7 7 7
3
0 0 -10
0 4 -2
-10 -2 5
3
-4 2 2
7 1 10
10 9 -1
2
9 -1
0 9
4
-7 2 -10 0
-5 1 -3 9
-10 -6 -3 3
8 -10 -...

output:

Yes
0 0 -1 
5 -10 0 
0 1 2 
5 -10 20 
2 -5 10 
0 3 -5 
No
No
No
Yes
2205 -266 -31 -3 
7056 -851 -99 -9 
630 -76 -9 0 
-2205 266 31 2 
7 0 0 0 
63 9 0 0 
-42 -76 1 0 
-7 -15 -11 1 
No
No
No
Yes
0 -1 
9 9 
9 0 
-9 1 
No
No
No
No
No
Yes
-24 -6 -7 
-12 -3 -3 
-12 -4 -4 
0 0 2 
0 -6 6 
-1 6 -12 
No
Yes
-...

result:

ok OK, Accepted. (10000 test cases)

Test #4:

score: 0
Accepted
time: 13ms
memory: 3892kb

input:

10000
3
10 3 10
0 10 0
9 7 0
4
-2 0 5 1
8 -8 -1 0
2 -9 -1 2
3 8 -5 -4
3
-7 0 7
6 7 -9
1 0 0
4
9 -10 1 -5
9 9 1 10
0 5 -8 -9
-8 -7 -6 -10
2
-10 -3
0 -10
4
5 2 4 2
4 -5 -7 8
-1 8 -5 -8
-9 6 0 6
3
9 0 0
1 0 3
6 3 2
2
8 -3
8 -5
4
6 0 0 6
0 -6 0 -6
0 0 0 10
8 -9 -10 -4
4
-9 -10 4 -1
0 -3 -4 -7
8 -3 -3 7
...

output:

No
No
No
No
Yes
-10 -3 
-30 -10 
10 0 
-30 1 
No
No
No
No
No
Yes
6 -7 
-3 3 
-3 0 
-3 1 
No
Yes
-10 -4 
-10 -5 
-5 0 
10 -2 
No
Yes
3 7 
0 1 
3 0 
0 1 
No
No
No
Yes
8 8 
0 -1 
8 8 
-7 -8 
No
Yes
-10 -1 -2 
20 0 5 
-10 0 -2 
-5 0 0 
12 -2 0 
20 0 1 
No
No
No
No
No
Yes
6 2 
0 1 
-2 -2 
9 6 
No
No
No
Y...

result:

ok OK, Accepted. (10000 test cases)

Test #5:

score: 0
Accepted
time: 9ms
memory: 3800kb

input:

10000
3
1 -1 0
0 4 0
1 3 9
3
5 6 6
10 -2 -5
10 -4 -7
3
-6 0 1
7 9 -8
0 0 -6
4
-10 4 9 -4
4 -2 3 -7
0 -8 0 -2
-1 -2 3 -4
4
0 0 0 -4
9 -10 0 7
1 0 0 3
-8 7 10 -5
4
-10 8 7 -1
5 4 7 10
-1 -7 0 1
-1 8 7 -4
3
7 0 0
10 7 -1
1 0 1
3
-5 0 -6
6 0 -1
1 7 1
3
-10 1 0
0 -8 -4
0 0 5
4
-9 4 -6 -5
-2 -10 2 4
4 7 -...

output:

Yes
-3 2 -1 
0 -2 0 
0 0 -1 
0 0 3 
0 -2 0 
-1 -3 -9 
No
Yes
0 0 1 
0 1 -8 
18 72 -6 
162 -36 0 
-41 9 0 
-6 0 1 
No
Yes
60 -14 8 -4 
-260 61 -23 7 
-60 14 -7 3 
60 -14 8 -5 
-10 0 10 0 
-40 -2 40 0 
9 -7 -10 0 
8 -7 -10 1 
No
Yes
7 -14 0 
0 -1 -1 
0 0 1 
-21 -14 0 
-11 -7 0 
1 0 1 
No
Yes
0 1 0 
-2...

result:

ok OK, Accepted. (10000 test cases)

Test #6:

score: 0
Accepted
time: 13ms
memory: 3808kb

input:

10000
3
6 0 0
-10 4 -7
8 0 6
2
8 -2
5 7
4
1 0 0 10
10 0 -10 -10
-6 -10 1 6
10 0 0 0
4
4 3 3 -3
-6 -8 -9 1
-9 -4 6 -6
9 0 -1 0
4
0 7 0 0
-2 7 -10 -1
-10 7 0 -1
0 2 0 7
4
2 -10 6 -2
5 -1 -7 3
3 8 -9 0
9 -6 5 -8
1
9
4
-5 7 -2 -2
-6 -2 -10 4
-1 -10 5 10
-1 -7 2 10
4
1 0 -3 -7
10 -10 4 -3
0 0 1 0
0 0 -3 ...

output:

Yes
-12 3 0 
-12 2 -7 
12 -2 6 
0 6 0 
2 24 0 
2 -4 1 
No
Yes
-600 12 122 61 
600 -11 -110 -50 
-300 6 61 30 
-100 2 20 10 
0 -2 0 0 
300 -100 0 -50 
-36 -10 1 6 
13 20 -2 -2 
No
Yes
-210 7 0 0 
0 0 0 -1 
0 0 1 -1 
-1540 51 -42 7 
35 0 -35 0 
1050 1 -1050 0 
-8 0 10 0 
2 -7 10 1 
No
Yes
3 
3 
No
Yes...

result:

ok OK, Accepted. (10000 test cases)

Test #7:

score: 0
Accepted
time: 13ms
memory: 3944kb

input:

10000
3
7 0 0
10 4 5
8 0 7
1
6
3
0 1 0
7 -3 0
5 -8 7
3
-2 -10 2
9 -3 2
-10 5 5
3
1 0 0
0 -2 0
4 9 -8
4
-2 -2 -4 -7
-1 -8 -4 7
4 10 -2 8
-1 4 -6 2
3
3 4 5
0 -2 0
-10 -6 0
4
10 0 10 -6
1 -2 9 10
-6 -7 -3 9
-5 9 -6 6
4
3 7 3 1
0 0 3 0
0 -10 3 0
0 1 3 -10
4
-1 -7 -10 1
5 2 1 -3
1 -4 5 4
6 -2 6 6
4
0 0 0...

output:

Yes
-42 7 0 
28 -4 5 
42 -6 7 
-14 -14 0 
-83 -84 0 
14 12 1 
No
No
No
Yes
-4 9 -2 
-4 8 -2 
0 0 1 
0 0 4 
1 2 0 
4 9 -8 
No
No
No
No
No
Yes
-25830 849 -120 10 
700 -23 3 -1 
2100 -69 10 0 
17220 -566 80 -7 
-7 0 0 0 
-210 -10 0 0 
21 -69 1 0 
0 21 12 1 
No
Yes
3 
3 
No
Yes
-4 5 
-4 4 
4 0 
4 1 
No
...

result:

ok OK, Accepted. (10000 test cases)

Test #8:

score: 0
Accepted
time: 9ms
memory: 3848kb

input:

10000
3
0 2 0
8 -7 -6
-3 -8 0
2
-2 9
1 6
4
-9 0 2 7
-2 0 0 0
-1 0 -8 0
-7 7 9 1
4
-8 -7 -9 2
9 7 -8 -8
2 2 0 10
9 9 -10 7
2
-9 0
-6 -9
3
6 7 9
2 7 -9
0 8 10
1
9
4
9 1 -10 -10
2 1 10 -1
-1 7 -1 -3
5 -7 10 8
3
0 0 10
-9 -4 9
-10 0 -4
4
-1 -3 2 -10
8 -7 4 4
1 -9 7 -1
-2 -1 7 -6
2
-6 9
9 0
3
-2 1 -2
-5 ...

output:

Yes
-6 -4 2 
0 0 -1 
54 37 -17 
-6 0 6 
5 3 -6 
-8 7 6 
No
Yes
0 23 -61 7 
28 214 0 0 
0 3 -8 0 
0 0 0 1 
-2912 2996 0 0 
381 -392 0 0 
143 -147 1 0 
-7 7 9 1 
No
Yes
9 -3 
0 1 
-3 -3 
-6 -9 
No
Yes
3 
3 
No
No
No
No
No
No
No
No
Yes
-448 1534 5 
-672 2301 7 
-28 96 0 
336 14 0 
98 4 0 
41 28 1 
No
N...

result:

ok OK, Accepted. (10000 test cases)

Test #9:

score: 0
Accepted
time: 13ms
memory: 3900kb

input:

10000
3
9 -3 0
0 10 0
0 -7 10
4
-2 -5 -8 5
-1 -1 -9 -3
-3 1 -2 0
-10 1 -8 4
3
8 7 5
0 -10 0
0 2 -5
4
9 -5 -4 -8
0 -4 -9 -9
-9 -4 -10 2
4 9 9 -9
4
2 0 -10 -9
0 0 9 0
-9 0 9 0
10 1 0 5
4
5 -9 3 -1
9 -10 9 -6
1 5 -5 4
-9 -2 -9 10
1
4
4
1 10 -10 0
9 -6 -8 -6
-9 2 2 -4
9 -7 -7 3
4
0 -2 5 0
0 -4 -3 -8
10 ...

output:

Yes
-30 -267 -9 
90 800 30 
0 0 -1 
240 -180 270 
-27 20 -30 
0 7 -10 
No
Yes
-20 -151 -19 
20 150 20 
0 0 1 
60 -40 80 
-8 5 -10 
0 2 -5 
No
No
No
Yes
2 
2 
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
1320 163 8 0 
0 0 0 -1 
-1320 -163 -9 6 
810 100 5 0 
-30 0 0 15 
240 1 0 -120 
60 -20 1 -30 
10 -2...

result:

ok OK, Accepted. (10000 test cases)

Test #10:

score: 0
Accepted
time: 13ms
memory: 3908kb

input:

10000
3
8 -4 -6
-6 10 0
0 1 0
3
-6 3 -9
10 8 -1
-3 -8 0
4
0 0 -1 3
-4 8 -6 5
0 0 9 0
6 0 10 2
1
10
3
9 5 2
0 0 -10
-8 0 9
3
8 1 -9
-10 3 4
-9 3 -9
4
-8 -6 1 -4
-10 0 0 10
4 0 0 0
8 10 0 0
4
0 -5 -10 8
10 -6 -2 -1
-10 -7 -2 -10
-7 -6 -10 -10
4
0 0 -9 -2
-1 -3 4 -6
0 0 0 -3
-9 0 0 9
4
10 7 -8 -5
-10 2...

output:

Yes
0 0 1 
6 -2 -3 
0 1 0 
3 0 -3 
0 1 0 
8 -4 -6 
No
No
No
Yes
40 329 2 
-180 -1480 -10 
160 1316 9 
60 -40 0 
-7 5 0 
-44 -20 1 
No
Yes
0 0 -1 -2 
0 0 2 5 
-20 -2 0 0 
0 1 0 0 
-1 -1 0 0 
8 10 0 0 
60 30 -5 0 
-26 -12 2 2 
No
Yes
27 -17 -81 -2 
0 -55 -212 -6 
27 -24 -108 -3 
-108 68 324 9 
63 -12 ...

result:

ok OK, Accepted. (10000 test cases)