## 【BZOJ 3534】[Sdoi2014] 重建

### Code

1A辣，撒花~ ★,°:.☆(￣▽￣)/\$:.°★

#include<iostream>
#include<cstdio>
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int MAXN = 51;
const double EPS = 1e-8;

int n;
double G[MAXN][MAXN],rev=1;

inline double Gauss(){
double ret = 1;
for (int j=1,w=j;j<=n;w=++j) {
for (int k=j+1;k<=n;k++) if (abs(G[j][k]) > abs(G[j][w])) w = k;
if (w != j) {for (int i=1;i<=n;i++) swap(G[i][j],G[i][w]); ret *= -1;}
for (int k=j+1;k<=n;k++) if (abs(G[j][k]) > EPS) {
double t = G[j][k] / G[j][j];
for (int i=1;i<=n;i++) G[i][k] -= G[i][j]*t;
} ret *= G[j][j];
} return ret;
}

int main(){
scanf("%d",&n);
for (int j=1;j<=n;j++) for (int i=1;i<=n;i++) scanf("%lf",&G[i][j]), rev *= i<j?1:1-G[i][j];
for (int j=1;j<=n;j++) for (int i=1;i<=n;i++) G[i][j] = G[i][j]/(1-G[i][j])*-1;
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i != j) G[i][i] -= G[j][i];
n--; printf("%.10lf\n",Gauss()*rev);
return 0;
}


## 【BZOJ 4031】[HEOI2015] 小Z的房间

#include<iostream>
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const LL MAXN = 100;
const LL MOD = 1000000000;

LL G[MAXN][MAXN],n,m,num[MAXN][MAXN],cnt;
char pat[MAXN];

inline int Gauss(){
for (LL j=1;j<=n;j++) for (LL i=1;i<=n;i++)
G[i][j] = (G[i][j]%MOD + MOD) % MOD;
LL ret = 1;
for (LL j=1;j<=n;j++) {
for (LL k=j+1;k<=n;k++) while (G[j][k]) {
LL t = G[j][j] / G[j][k];
for (LL i=1;i<=n;i++) G[i][j] = ((G[i][j] - G[i][k]*t) % MOD + MOD) % MOD;
for (LL i=1;i<=n;i++) swap(G[i][j], G[i][k]); ret *= -1; ret = (ret%MOD + MOD) % MOD;
}
ret = (G[j][j]*ret%MOD + MOD) % MOD;
} return ret;
}

inline void AddEdge(LL u, LL v){
G[u][u]++; G[v][v]++;
G[u][v]--; G[v][u]--;
}

int main(){
scanf("%d%d",&m,&n);
for (LL j=1;j<=m;j++) {
scanf("%s",pat+1);
for (LL i=1;i<=n;i++) if (pat[i] == '.') {
num[i][j] = ++cnt;
}
} n = cnt-1; printf("%d\n",Gauss());
return 0;
}


## 【BZOJ 2467】[中山市选2010] 生成树

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 400+9;
const int MOD = 2007;

int G[MAXN][MAXN],n;

char c=getchar(); int ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0') ret=ret*10+c-'0', c=getchar();
return ret;
}

inline int id(int i, int j){
if (i>n) i -= n;
return (--i)*4+j;
}

inline void Add_Edge(int u, int v){
G[u][u]++; G[v][v]++;
G[u][v]--; G[v][u]--;
}

inline void Build_Matrix(){
for (int i=1;i<=n;i++) {
for (int j=1;j<=3;j++) Add_Edge(id(i,j),id(i,j+1));
}n *= 4; n--;
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) G[i][j] = (G[i][j]%MOD + MOD) % MOD;
}

inline int Gauss(){
int ret = 1;
for (int j=1,w=0;j<=n;j++) {
for (int k=j+1;k<=n;k++) while (G[j][k]) {
int t = G[j][j]?G[j][k] / G[j][j]:1;
for (int i=1;i<=n;i++) G[i][k] = ((G[i][k] - G[i][j]*t) % MOD + MOD) % MOD;
for (int i=1;i<=n;i++) swap(G[i][k], G[i][j]); ret *= -1;
} ret = ret*G[j][j] % MOD;
} return (ret + MOD) % MOD;
}

int main(){
for (int T=read();T;T--) {
n = read(); memset(G,0,sizeof(G));
Build_Matrix();
printf("%d\n",Gauss());
}
return 0;
}