SPOJ Highways and Find the Determinant lll(Count the spanning trees)

Description of Highways

给出原图(无向图)，求裸的生成树计数

Description of Find the Determinant III

求方阵A的行列式的值模P的值

Code of Highways

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int N = 55;

int n, m;
ll b[N][N];

ll Gauss()
{
    ll res = 1;
    ///i start from 2 : throw away first row and first column
    for(int i = 2; i <= n; ++i)
    {
        for(int j = i + 1; j <= n; ++j)
        {
            while(b[j][i])
            {
                ll t = b[i][i] / b[j][i];
                for(int k = i; k <= n; ++k)
                    b[i][k] -= b[j][k] * t;
                for(int k = i; k <= n; ++k)
                    swap(b[i][k], b[j][k]);
                res *= -1;
            }
        }
        if(b[i][i] == 0)
            return 0;
        res *= b[i][i];
    }
    return res > 0 ? res : -res;
}

int main()
{
    int _;
    scanf("%d", &_);
    while(_--)
    {
        scanf("%d %d", &n, &m);
        memset(b, 0,sizeof(b));
        int u, v;
        while(m--)
        {
            scanf("%d %d", &u, &v);
            b[u][u]++, b[v][v]++, b[u][v] = b[v][u] = -1;
        }
        cout << Gauss() << '\n';
    }
    return 0;
}

注意建图(基尔霍夫矩阵)

Code of Find The Determinant III

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define MOD(x) ((x % m) + m) % m
const int N = 210;

int n, m;
ll b[N][N];

ll Gauss()
{
    ll res = 1;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = i + 1; j <= n; ++j)
        {
            while(b[j][i])
            {
                ll t = b[i][i] / b[j][i];
                for(int k = i; k <= n; ++k)
                    b[i][k] = MOD(b[i][k] - b[j][k] * t);
                for(int k = i; k <= n; ++k)
                    swap(b[i][k], b[j][k]);
                res *= -1;
            }
        }
        if(b[i][i] == 0)
            return 0;
        res = MOD(res * b[i][i]);
    }
    return res > 0 ? res : -res;
}

int main()
{
    while(~scanf("%d %d", &n, &m))
    {
        memset(b, 0,sizeof(b));
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
            {
                scanf("%lld", &b[i][j]);
                b[i][j] = MOD(b[i][j]);
            }
        cout << Gauss() << '\n';
    }
    return 0;
}

注意不能再求主子式的行列式了，就是求原行列式

注意取模