MIFF - Matrix inverse

no tags 

Let p a prime number. A set Fp={0, 1 ... p-1} equipped with the mod p addition and multiplication is a finite field. In this problem you have to compute the multiplicative inverse of some Fp valued (quadratic) matrices.

The input consists of blocks. The structure of a block is:

n p

A1, 1 ... A1, n

...

An, 1 ... An, n

where p is a prime number, 1ij are in Fp. The last block followed by 0 0.

 

The output for each block is either the multiplicative inverse of a given matrix if it exists or the word "singular"

Example

Input:

4 2
1 1 1 1
1 1 0 1
0 0 0 1
0 1 0 1

3 7
3 5 0
0 5 1
6 6 6

2 2
1 1
1 0

3 5
4 0 0
2 4 1
0 2 3

3 7
0 1 4
6 1 2
2 1 1

0 0

Output:

0 1 0 1
0 0 1 1
1 1 0 0
0 0 1 0

6 3 3
5 1 1
3 3 2

0 1
1 1

singular

singular

hide comments
.:frUstrAteD:.: 2015-09-27 08:31:58

inbuilt swap function doesn't work for pointer to an array -_-

(Tjandra Satria Gunawan)(曾毅昆): 2012-06-04 20:31:11

help me... I'm getting WA... :(
FINALLY AC!!!

Last edit: 2012-08-09 17:32:55

Added by:czylabsonasa
Date:2011-10-26
Time limit:1.116s
Source limit:22222B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:folklore