class="markdown_views prism-atelier-sulphurpool-light"> 先贴一波知乎的问题：行列式的本质是什么？ (虽然本蒟蒻自己都没怎么看) 对于一个矩阵的行列式，有很多性质
如下面的这个矩阵：
[123456789] " role="presentation">⎡⎣⎢147258369⎤⎦⎥ $$\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right]$$
我们可以把它变成这样：
123|123|123456|456|456789|789|789 " role="presentation">147258369|||147258369|||147258369 $$\begin{array}{cccccccccccc}& 1& 2& 3& |& 1& 2& 3& |& 1& 2& 3\\ & 4& 5& 6& |& 4& 5& 6& |& 4& 5& 6\\ & 7& 8& 9& |& 7& 8& 9& |& 7& 8& 9\end{array}$$
于是行列式就是
每条黑 {MOD}连线上的数相乘之和减去每条红 {MOD}连线上的数相乘之和。(如有错误，欢迎指正) 那么可以发现，若该连线上有任何一个数为0，这条线就作废了（贡献为0）。这也给了我们不同暴力而用更优的方法求解矩阵行列式的机会。 于是我们可以构造一个上三角矩阵，可以发现：在上三角矩阵里，行列式即为矩阵对角线上的数的乘积。因为其他线上都有0了。还是按上面的图来讲，4，7，8的位置为0了，于是两条黑线三条红线都废了。 在构造上三角矩阵的过程中，我们可以模仿欧几里得求gcd的过程。 代码如下： inline int getdet() { int det=1;int flag=0; for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { int x=i,y=j; while(a[y][i]!=0) { int t=a[x][i]/a[y][i]; for(int k=i;k<=n;k++) a[x][k]-=t*a[y][k] swap(x,y); } if(x!=i){ for(int k=1;k<=n;k++){ swap(a[x][k],a[i][k]); } flag^=1; } } if(a[i][i]==0) return 0; det=det*a[i][i]%mod; } if(flag) det=-det; return det; }

---

upd:在bzoj1494: [NOI2007]生成树计数中学习到另外一种非常便于手算的求行列式方法：