ZOJ month contest D.Determinant and Matrix

ACM
  1. 1. Input
  2. 2. Output
  3. 3. Sample Input
    1. 3.0.1. Sample Output

Time Limit: 2 Seconds Memory Limit: 65536 KB

##Description
Recently, LBH is learning the curse linear algebra. Thus he is very interested in matrix and determinant now. In order to practice his ability of solving the problem of linear algebra, he just invent some problems by himself. Once the problems was create, he would solve it immediately. However, he meet a problem that was so hard that he couldn’t work out even though racked his brains. The problem was described as follow:

To a integer martix Mnn(aij), we define two function add(Mnn(aij))=Mnn(aij + 1) and sub(Mnn(aij))=Mnn(aij - 1) which were exactly like this:

DeterminantAndMatrixFig1

DeterminantAndMatrixFig2

According to the martix Mnn(aij), we can permutate it and get a full permutation set Perm(Mnn(aij)) = {Mnn(aIiJj)| I and J is a permutation of 1..n }, (Perm(M) is a set, each matrix in Perm(M) is unique). For example:

DeterminantAndMatrixFig3

The problem is to get the result of a fomula about an integer matrix Mnn:

DeterminantAndMatrixFig4

in which the det(M) meaned to cacluate the determinant of M.

Input

There are several test cases.

The first line contains an integer T(T ≤ 100) . Then T test cases follow.

In each test case, the first line contains one integer n(0< n≤ 10). The number means the giving matrix’s size is n×n

Then there are n lines followed, each line contains n integers aij(-10≤ aij≤ 10), in the position row i, colum j, it represents the number aij.

Output

For each test case, since the result may be very large, output one line with the result modulo 230.

Sample Input

1
2
3
4
1
2
1 1
1 2

Sample Output

1
2

Author: LIN, Binghui
Source: ZOJ Monthly, August 2014



这道题全场现场只A了一个人。今天我们比赛的时候我A了,挺爽的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
import java.util.Scanner;
import java.math.*;
public class Main {
static long fact[]=new long[15];
static long kind;
static int A[][]=new int[10][10];
static final BigInteger MOD=BigInteger.valueOf(1&lt;&lt;30);
static void getKind(int n){
boolean mark[]=new boolean[10];
for(int i,j,k,r=0;r&lt;2;r++){
for (i = 0; i &lt; n; ++ i) mark[i] = false;
for (i = 0; i &lt; n; ++ i) {
if (mark[i]) continue;
int cnt = 0;
for (j = i; j &lt; n; ++ j) {
for (k = 0; k &lt; n; ++ k) {
if (r==1&amp;&amp;A[k][i] != A[k][j])break;
if(r==0&amp;&amp;A[i][k] != A[j][k])break;
}
if (k == n) {
++ cnt;
mark[j] = true;
}
}
kind /= fact[cnt];
}
}
}
public static void main(String[] args){
Scanner cin=new Scanner(System.in);
int n,T=cin.nextInt();
fact[0]=1;
for(int i=1;i&lt;=10;i++)fact[i]=fact[i-1]*i;
while(T--&gt;0){
n=cin.nextInt();
for(int i=0;i&lt;n;i++){
for(int j=0;j&lt;n;j++){
A[i][j]=cin.nextInt();
}
}
long res=0;
Matrix matrix=new Matrix(n);
kind=fact[n]*fact[n];
getKind(n);
if(kind%2==1){
matrix.valueOf(A, 0);
res=res ^(matrix.Det().mod(MOD).longValue());
}
matrix.valueOf(A, 1);
res=res^(matrix.Det().mod(MOD).longValue());
matrix.valueOf(A, -1);
res=res^(matrix.Det().mod(MOD).longValue());
System.out.println(res);
}
cin.close();
}
}
class Matrix{
BigInteger M[][]=new BigInteger[10][10];
BigInteger ZERO,ONE;
int n;
Matrix(int n){
this.n=n;
ZERO=BigInteger.ZERO;
ONE=BigInteger.ONE;
}
void valueOf(int A[][],int d){
for(int i=0;i&lt;n;i++){
for(int j=0;j&lt;n;j++){
M[i][j]=BigInteger.valueOf(A[i][j]+d);
}
}
}
BigInteger Det(){
BigInteger tmp, res = ONE, div = ONE;
int i, j, k;
for (i = 0; i &lt; n; ++ i) {
for (j = i; j &lt; n; ++ j) {
if (!M[j][i].equals(ZERO)) break;
}
if (j == n) return ZERO;
if (j != i) {
//res = res.negate();
for (k = 0; k &lt; n; ++ k) {
tmp = M[j][k];
M[j][k] = M[i][k];
M[i][k] = tmp;
}
}
res = res.multiply(M[i][i]);
for (j = i + 1; j &lt; n; ++ j) {
if (M[j][i].equals(ZERO)) continue;
div = div.multiply(M[i][i]);
for (k = i + 1; k &lt; n; ++ k) {
M[j][k] = M[j][k].multiply(M[i][i]).subtract(M[i][k].multiply(M[j][i]));
}
}
}
res = res.divide(div);
if (res.compareTo(ZERO) &lt; 0) res = res.negate();
return res;
}
}