【BZOJ4031】小Z的房间
Zarxdy34
posted @ 2015年10月21日 16:17
in BZOJ
with tags
Matrix-Tree定理
, 571 阅读
据说数据有非法字符，exited，成功爆了我的读入。
Matrix-Tree定理，算行列式时消元用辗转相除法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include <cmath>#include <cstdio>#include <cstring>#include <algorithm>typedef long long LL;using namespace std;const int maxn=12,mo=1000000000;inline char readchar() {char ch;while (!((ch=getchar())=='.' || ch=='*'));return ch;}struct Matrix{ int a[maxn*maxn][maxn*maxn]; int n; int* operator[] (int x) {return a[x];} int det() { int ans=1; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) a[i][j]=(a[i][j]%mo+mo)%mo; for (int i=1;i<n;i++) { for (int j=i+1;j<=n;j++) while (a[j][i]) { int x=a[i][i]/a[j][i]; for (int k=i;k<=n;k++) a[i][k]=(a[i][k]-1ll*x*a[j][k]%mo+mo)%mo; for (int k=i;k<=n;k++) swap(a[i][k],a[j][k]); ans=-ans; } } if (ans==-1) ans+=mo; for (int i=1;i<=n;i++) ans=1ll*ans*a[i][i]%mo; return ans; }}M;int id[maxn][maxn],ids;int n,m;int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (readchar()=='.') id[i][j]=++ids; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (id[i][j]) { if (i>1 && id[i-1][j]) M[id[i][j]][id[i][j]]++,M[id[i][j]][id[i-1][j]]=-1; if (i<n && id[i+1][j]) M[id[i][j]][id[i][j]]++,M[id[i][j]][id[i+1][j]]=-1; if (j>1 && id[i][j-1]) M[id[i][j]][id[i][j]]++,M[id[i][j]][id[i][j-1]]=-1; if (j<m && id[i][j+1]) M[id[i][j]][id[i][j]]++,M[id[i][j]][id[i][j+1]]=-1; } M.n=ids-1; printf("%d\n",M.det()); return 0;} |
评论 (0)
