math - GaussMod

const int MOD = 2;
// Gaussian Modular Solution. 0 based Indexing, Complexity: eq^2 * var
struct GaussMod{
    typedef long long  T;
    void show(vector< vector<T> > A){
        for(int i = 0 ; i < A.size(); i ++ ) {
            for(int j = 0; j < A[i].size(); j ++ ) printf("%4lld",A[i][j]);
            printf("\n");
        }
    }
    long long extended_euclid(long long a, long long b, long long &x, long long &y) {
        long long xx = y = 0;
        long long yy = x = 1;
        while (b) {
            long long q = a / b;
            long long t = b; b = a%b; a = t;
            t = xx; xx = x - q*xx; x = t;
            t = yy; yy = y - q*yy; y = t;
        }
        return a;
    }
    long long mod(long long a, long long b) {
        return ((a%b) + b) % b;
    }
    // computes b such that ab = 1 (mod n), returns -1 on failure
    long long inv(long long a,long long n)
    {
        long long x, y;
        long long g = extended_euclid(a, n, x, y);
        if (g > 1) return -1;
        return mod(x, n);

    }


    int gauss(vector< vector<T> >& A) {
        int m = A.size(), n = A[0].size() - 1;
        int i = 0, j = 0;
        while (i < m && j < n) {
            int r = i;
            for (int k = i; k < m; k++) {
                if (A[k][j]) {
                    r = k;
                    break;
                }
            }
            if (r != i) for (int k = 0; k <= n; k++) swap(A[i][k], A[r][k]);
            if (A[i][j] == 0) {
                j++;
                continue;
            }

            for (int k = 0; k < m; k++) {
                if (A[k][j] == 0 || i == k) continue;
                long long f = A[k][j] * inv(A[i][j], MOD ) % MOD ;

                for (int t = j; t <= n; t++) A[k][t] = ((A[k][t] - f * A[i][t]) % MOD  + MOD ) % MOD ;
            }


            i++;
        }
        for (int k = i; k < m; k++) if (A[k][n]) return 0; // no solution
        if (i < n) return 2; // many solution
        return 1; // unique solution
    }

    vector< pair<int,T > > FindSolution(vector< vector<T> > A) // returns solution (x,v) form, x=0,Multiple,1-unique. v=root
    {

        vector<pair<int,T> > res(A[0].size() - 1, mp(0,-1));
        for(int i = 0; i < A.size(); i ++ ) {
            for(int j = 0; j < A[i].size() - 1; j ++ ) {
                if(A[i][j]) {
                    res[j] = make_pair(1, A[i].back());
                    break;
                }
            }
        }
        return res;
    }
};