Luogu4111 [HEOI2015]小Z的房间 （矩阵树，辗转相除高斯消元）

除法不能用于同余系，要辗转相除。注意不能加入柱子到矩阵。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define R(a,b,c) for(register int  a = (b); a <= (c); ++ a)

#define nR(a,b,c) for(register int  a = (b); a >= (c); -- a)

#define Max(a,b) ((a) > (b) ? (a) : (b))

#define Min(a,b) ((a) < (b) ? (a) : (b))

#define Fill(a,b) memset(a, b, sizeof(a))

#define Abs(a) ((a) < 0 ? -(a) : (a))

#define Swap(a,b) a^=b^=a^=b

#define ll long long

#define ON_DEBUG

#ifdef ON_DEBUG

#define D_e_Line printf("\n\n----------\n\n")

#define D_e(x)  cout << #x << " = " << x << endl

#define Pause() system("pause")

#define FileOpen() freopen("in.txt","r",stdin);

#else

#define D_e_Line ;

#define D_e(x)  ;

#define Pause() ;

#define FileOpen() ;

#endif

struct ios{

    template<typename ATP>ios& operator >> (ATP &x){

        x = 0; int f = 1; char c;

        for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-')  f = -1;

        while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();

        x*= f;

        return *this;

    }

}io;

using namespace std;

const int N = 107;

const int mod = 1000000000;

int n, m;

int a[N][N];

//inline void Gauss(int n){

//	R(i,1,n){

//		int r = i;

//		R(j,i + 1,n){

//			if(Abs(a[r][i]) > Abs(a[i][i])){

//				r = i;

//			}

//		}

//		if(a[r][i] == 0){

//			printf("0");

//			return;

//		}

//		swap(a[r], a[i]);

//		R(j,i + 1,n){

//			int t = a[j][i] / a[i][i];

//			R(k,1,n){

//				a[j][k] -= t * a[i][k];

//			}

//		}

//	}

//	long long ans = 1;

//	R(i,1,n) ans = 1ll * ans * a[i][i] % mod;

//	printf("%lld", ans);

//}

inline void Gauss(int n){

	int ans = 1;

	R(i,1,n){

		R(j,i + 1,n){

			while(a[j][i]){

				int t = a[i][i] / a[j][i];

				R(k,1,n){

					a[i][k] = (a[i][k] - 1ll * t * a[j][k] % mod + mod) % mod;

				}

				swap(a[i], a[j]);

				ans = -ans;

			}

		}

		ans = (1ll * ans * a[i][i] % mod + mod) % mod;

	}

	printf("%d", ans);

}

int mp[N][N], mpIndex;

char str[N][N];

inline void add(int x, int y){

	++a[x][x];

	++a[y][y];

	--a[x][y];

	--a[y][x];

}

int main(){

	io >> n >> m;

	R(i,1,n){

		scanf("%s", str[i] + 1);

	}

	R(i,1,n){

		R(j,1,m){

			if(str[i][j] == '.'){

				mp[i][j] = ++mpIndex;

			}

		}

	}

	R(i,1,n){

		R(j,1,m){

			if(str[i][j] == '.'){

				if(str[i - 1][j] == '.'){

					add(mp[i][j], mp[i - 1][j]);

				}

				if(str[i][j - 1] == '.'){

					add(mp[i][j], mp[i][j - 1]);

				}

			}

		}

	}

	Gauss(mpIndex - 1);

	return 0;

}

Luogu4111 [HEOI2015]小Z的房间 （矩阵树，辗转相除高斯消元）的相关教程结束。