Find The Determinant III

問題

N*N(N<=200)の行列Aと，正整数Pが与えられるので，Aの行列式をmod Pで求めよ．

解法

正統な解法はkomiyaさんの記事参照．
[id:komiyam:20111216:1323963329]

ここでは，逆元とかを使わずに直接求めた．
例えば，以下のような3*3の行列の場合を考える．
5,9,1
3,2,3
8,5,6
まず，1列目について最も値が小さい行を持ってくる．
3,2,3
5,9,1
8,5,6
次に，2行目以降の1列目（5と8）が出来るだけ小さくなるように，1行目を引く．
3,2,3
2,7,-2
2,1,0
そうしたら，さっきと同じ操作を行う．
2,1,0
0,6,-2
1,1,3
こういうユークリッドの互助法ライクな事を繰り返すと，（最終的に）必ず1列目に存在する非零が1つだけになる．これらの操作には，逆元や中国剰余定理等が必要ない．
但し，反復回数が結構あるのでTLEギリギリ．ピボットのようなものの候補に他の列を入れるとちょっと早くなる．

簡易コード

int detMod(int[][] A_, int mod){
	int n=A_.length, det=1;
	int[][] A=new int[n][n];
	for(int j=0; j<n; j++)
		for(int i=0; i<n; i++)
			A[j][i]=(A_[j][i]%mod+mod)%mod;
	for(int k=0; k<n; k++){
		for(;;){
			int nonZero=0;
			for(int j=k; j<n; j++){
				if(A[j][k]==0) continue;
				nonZero++;
				if(A[k][k]==0||A[j][k]<A[k][k]){
					int[] t=A[k]; A[k]=A[j]; A[j]=t;
					det=(-det+mod)%mod;
				}
			}
			if(nonZero==0) return 0;
			if(nonZero==1) break;
			for(int j=k+1; j<n; j++){
				int r=A[j][k]/A[k][k];
				for(int i=k; i<n; i++)
					if((A[j][i]=A[j][i]-(int)((long)A[k][i]*r%mod))<0)
						A[j][i]+=mod;
			}
		}
		det=(int)((long)det*A[k][k]%mod);
	}
	return det;
}