评测记录1

评测记录2

两份代码只有辗转相除的部分有差别：

//评测记录1(AC)
for(int j=i+1;j<=n;++j){
	while(a[i][i]){
		int t=a[j][i]/a[i][i];
		for(int k=i;k<=n;++k){
			a[j][k]=(a[j][k]-1ll*t*a[i][k]%mod+mod)%mod;
		}
		swap(a[i],a[j]);fh=-fh;
	}
	swap(a[i],a[j]),fh=-fh;
}

//评测记录2(TLE)
for(int j=i+1;j<=n;++j){
	while(a[j][i]){
		int t=a[i][i]/a[j][i];
		for(int k=i;k<=n;++k){
			a[i][k]=(a[i][k]-1ll*t*a[j][k]%mod+mod)%mod;
		}
		swap(a[i],a[j]);fh=-fh;
	}
}

上述代码是将矩阵 $a$ 的第 $i$ 行与第 $j$ 行辗转相减，以达到 a[j][i]=0 的效果。

两份代码原理上应该是一样的，其效果应该类似于求gcd(x,y)中交换 $x$ 和 $y$ ，应该最多有一次运算的差距，请问为什么会出现如此大的差别？