Graph Coloring - LightOJ

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int64_t MOD = 1e9+7;

int64_t extended_gcd(int64_t a, int64_t b, int64_t &x, int64_t &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int64_t g = extended_gcd(b, a%b, y, x);
    y -= x*(a/b);
    return g;
}
inline int64_t modSum(int64_t a, int64_t b, int64_t mod = MOD) {
    return (a+b >= mod ? a+b-mod : a+b);
}
inline int64_t modSub(int64_t a, int64_t b, int64_t mod = MOD) {
    return (a-b < 0 ? a-b+mod : a-b);
}
inline int64_t modMul(int64_t a, int64_t b, int64_t mod = MOD) {
    return (a*b)%mod;
}
int64_t inv_mod(int64_t a, int64_t m = MOD) {
    int64_t x, y;
  extended_gcd(a, m, x, y);
    return (x%m + m)%m;
}
int64_t modDiv(int64_t a, int64_t b, int64_t mod = MOD) {
    return modMul(a, inv_mod(b, mod), mod);
}
int64_t binpow(int64_t base, int exp, int mod = MOD) {
    int64_t ans = 1;
    while (exp > 0) {
        if (exp & 1) ans = modMul(ans, base, mod);
        base = modMul(base, base, mod);
        exp >>= 1;
    }
    return ans;
}

template<typename T>
struct Matrix {
    std::vector<std::vector<T>> mat;
    Matrix(int n, int m, bool id = false) {
        mat.resize(n, std::vector<T>(m, 0));
        if (id) for (int i = 0; i < n; ++i)
            mat[i][i] = 1;
    }
};

// Gaussian elimination with partial pivot (avoids propagation of rounding errors)
pair<int, int> gaussianElimination(Matrix<int64_t> a, Matrix<int64_t> &ans, int64_t k) {
    int n = (int)a.mat.size();
    int m = (int)a.mat[0].size()-1;
    std::vector<int> end(m, -1);

    for (int col = 0, row = 0; col < m and row < n; ++col) {
        int l = row;

        // Which row has largest column value
        for (int i = row; i < n; ++i)
            if (abs(a.mat[i][col]) > abs(a.mat[l][col]))
                l = i;
        if (a.mat[l][col] == 0)
            continue;
        for (int i = col; i <= m; ++i)
            swap(a.mat[row][i], a.mat[l][i]);
        end[col] = row;

        // Elimination phase
        for (int i = 0; i < n; ++i) if (i != row) {
            int64_t c = modDiv(a.mat[i][col], a.mat[row][col], k);
            for (int j = m; j >= col; --j) {
                a.mat[i][j] = modSub(a.mat[i][j], modMul(a.mat[row][j], c, k), k);
            }
        }
        ++row;
    }

    // Substitution phase
    for (int i = 0; i < m; ++i)
        if (end[i] != -1)
            ans.mat[i][0] = modDiv(a.mat[end[i]][m], a.mat[end[i]][i], k);

    for (int i = 0; i < n; ++i) {
        int64_t sum = 0;
        for (int j = 0; j < m; ++j)
            sum = modSum(sum, modMul(ans.mat[j][0], a.mat[i][j], k), k);
        if (sum != a.mat[i][m])
            return {0, 0}; // No solution
    }

    int cnt = 0;
    for (int i = 0; i < m; ++i)
        if (end[i] == -1)
            ++cnt;

    if (cnt) return {INF, cnt}; // Infinite solutions

    return {1, 0}; // One solution
}

int tc;
int n, m;
int64_t k;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> tc;
    for (int t = 1; t <= tc; ++t) {
        cout << "Case " << t << ": ";
        cin >> n >> m >> k;
        vector<vector<int>> gr(n, vector<int>());
        for (int i = 0, a, b; i < m; ++i) {
            cin >> a >> b, --a, --b;
            gr[a].push_back(b);
            gr[b].push_back(a);
        }
        Matrix<int64_t> a(n, n+1);
        for (int i = 0; i < n; ++i) {
            a.mat[i][i] = 1;
            for (int to : gr[i]) {
                a.mat[i][to] = k-1;
            }
        }
        Matrix<int64_t> ans(n, 1);
        auto [ret, qtd] = gaussianElimination(a, ans, k);
        if (ret <= 1) {
            cout << ret << '\n';
        } else {
            cout << binpow(k, qtd, MOD) << '\n';
        }
    }
}