隨筆檔案(16)

/*
????求行列式?O(n^3)
*/
#?include? < string .h >

int ?v[N][N],?t[N];

int ?gcd( int ?a,? int ?b)?{ return ?b? ? ?gcd(b,?a % b):a;}

int ?det( int ?n)
{
???? int ?c,?r,?i;
???? int ?cof? = ? 1 ,?ret? = ? 1 ;
???? int ?mc,?mh;
????
???? for ?(c? = ? 1 ;?c? <= ?n;? ++ c)
????{
???????????? for ?(r? = ?c;?r? <= ?n;? ++ r)
????????????{
???????????????????? if ?(v[r][c]? < ? 0 )? for ?(i? = ?c;?i? <= ?n;? ++ i)?v[r][i]? = ? - v[r][i];
???????????????????????? for ?(tt? = ? 0 ,?i? = ?c;?i? <= ?n;? ++ i)? if ?(v[r][i]? != ? 0 )
???????????????????????????????????? if ?(tt? == ? 0 )?tt? = ?v[r][i];
???????????????????????????????????? else ?tt?? = ?gcd(v[r][i],?tt);
???????????????????????? if ?(tt? < ? 0 )?tt? = ? - tt;
???????????????????????? if ?(tt? > ? 1 )? for ?(i? = ?c;?i? <= ?n;? ++ i)?v[r][i]? /= ?tt;
????????????????}
???????? for ?(mv? = ?v[ 1 ][c],?mr = ?c,?r? = ?c + 1 ;?r? <= ?n;? ++ r)
????????{
???????????? if ?(v[r][c]? < ? 0 )? for ?(ret? = ? - ret,?i? = ?c;?i? <= ?n;? ++ i)?v[r][i]? *= ? - 1 ;
???????????? if ?(v[r][c]? > ?mv)?mv? = ?m[r][c],?mr? = ?r;
????????}
????????
???????? /* ?行列式整列都為?0? */
???????? if ?(mv? == ? 0 )? return ? 0 ;
????????
???????? /* ?交換行使?v[c][c]?是?v[cn][c]?中最大的? */
????????memcpy(t + 1 ,?v[ 1 ] + 1 ,? sizeof (v[ 0 ][ 0 ]) * n);
????????memcpy(v[ 1 ] + 1 ,?v[mr] + 1 ,? sizeof (v[ 0 ][ 0 ]) * n);
????????memcpy(v[mr] + 1 ,?t + 1 ,? sizeof (v[ 0 ][ 0 ]) * n);
????????
???????? /* ?消去?c+1..n?行行首非零元素? */
???????? for ?(r? = ?c + 1 ;?r? <= ?n;? ++ r)? if ?(v[r][c])
????????{
????????????mh? = ?v[r][c] / gcd(mv,?v[r][c]));
????????????mc? = ?mv * mh / v[r][c];
???????????? for ?(t? = ?c;?t? <= ?n;? ++ c)?????v[r][t]? = ?mc * v[r][t] - mh * v[c][t];
????????????cof? *= ?mc;
????????}
????????ret? *= ?v[c][c];
????}
????
???? return ?ret * mc;
}