背结论 : 度-邻
CODE1
O(n3logn)O(n^3logn)O(n3logn)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template<class T>inline void read(T &num) {
register char ch; register int flg = 1;
while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;
for(num=0; isdigit(ch); num=num*10+ch-'0', ch=getchar());
num *= flg;
}
const int MAXN = 85;
const int mod = 1e9;
int n, m, tot, id[10][10];
int a[MAXN][MAXN], d[MAXN][MAXN], g[MAXN][MAXN];
char s[10];
inline void link(int u, int v) {
++d[u][u], ++d[v][v];
++g[u][v], ++g[v][u];
}
inline int Gauss(int N) { //高斯消元成上三角
int ans = 1;
for(int i = 1; i <= N; ++i) {
for(int k = i+1; k <= N; ++k)
while(a[k][i]) { //这里有一个log
int d = a[i][i] / a[k][i];
for(int j = i; j <= N; ++j)
a[i][j] = ((a[i][j] - 1ll * d * a[k][j] % mod) % mod + mod) % mod;
swap(a[i], a[k]), ans = -ans; //注意每交换两行都要取反
}
ans = (1ll * ans * a[i][i] % mod + mod) % mod;
}
return ans;
}
int main() {
read(n), read(m);
for(int i = 1; i <= n; ++i) {
scanf("%s", s+1);
for(int j = 1; j <= m; ++j)
if(s[j] != '*') {
id[i][j] = ++tot;
if(id[i-1][j]) link(tot, id[i-1][j]);
if(id[i][j-1]) link(tot, id[i][j-1]);
}
}
for(int i = 1; i < tot; ++i)
for(int j = 1; j < tot; ++j)
a[i][j] = d[i][j] - g[i][j];
printf("%d\n", (Gauss(tot-1) + mod) % mod);
}
CODE2
O(n3+n2logn)→O(n3)O(n^3+n^2logn)\to O(n^3)O(n3+n2logn)→O(n3)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template<class T>inline void read(T &num) {
register char ch; register int flg = 1;
while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;
for(num=0; isdigit(ch); num=num*10+ch-'0', ch=getchar());
num *= flg;
}
const int MAXN = 85;
const int mod = 1e9;
int n, m, tot, id[10][10];
int a[MAXN][MAXN], d[MAXN][MAXN], g[MAXN][MAXN];
char s[10];
inline void link(int u, int v) {
++d[u][u], ++d[v][v];
++g[u][v], ++g[v][u];
}
inline void kill(int a, int b, int &ii, int &ik, int &ki, int &kk, int &sign) {
ii = 1, ik = 0;
ki = 0, kk = 1;
sign = 1;
while(b) {
(ii -= a/b * ki) %= mod;
(ik -= a/b * kk) %= mod;
a -= a/b * b;
swap(a, b);
swap(ii, ki);
swap(ik, kk);
sign = -sign;
}
}
inline int Gauss(int N) {
int ans = 1, ii, ik, ki, kk, sign;
for(int i = 1; i <= N; ++i) {
for(int k = i+1; k <= N; ++k) if(a[k][i]) {
kill(a[i][i], a[k][i], ii, ik, ki, kk, sign); //先把系数算出来
ans *= sign;
for(int j = i; j <= N; ++j) {
int _aij = (1ll * a[i][j] * ii + 1ll * a[k][j] * ik) % mod;
int _akj = (1ll * a[i][j] * ki + 1ll * a[k][j] * kk) % mod;
a[i][j] = _aij, a[k][j] = _akj;
}
}
ans = 1ll * ans * a[i][i] % mod;
}
return ans;
}
int main() {
read(n), read(m);
for(int i = 1; i <= n; ++i) {
scanf("%s", s+1);
for(int j = 1; j <= m; ++j)
if(s[j] != '*') {
id[i][j] = ++tot;
if(id[i-1][j]) link(tot, id[i-1][j]);
if(id[i][j-1]) link(tot, id[i][j-1]);
}
}
for(int i = 1; i < tot; ++i)
for(int j = 1; j < tot; ++j)
a[i][j] = d[i][j] - g[i][j];
printf("%d\n", (Gauss(tot-1) + mod) % mod);
}