bzoj4031: [HEOI2015]小Z的房间-Matrix Tree/行列式

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<string>
 5 #include<cstring>
 6 #include<algorithm>
 7 using namespace std;
 8 namespace Moxing {
 9     const int mod=1000000000;
10     int n,m,cnt,k[95][95];int a[95][95],d[95][95],idx[11][11];
11     char s[11][11];
12     bool check(int x,int y) {
13         return (x>=1)&&(x<=n)&&(y>=1)&&(y<=m)&&(s[x][y]==‘.‘);
14     }
15     long long gauss() {
16         long long ans=1;
17         for(int j=1;j<=cnt;j++){
18             for(int i=j+1;i<=cnt;i++){
19                 while(k[i][j]){
20                     long long t=k[j][j]/k[i][j];
21                     for(int g=j;g<=cnt;g++){
22                         k[j][g]=(k[j][g]-t*k[i][g]%mod+mod)%mod;
23                         swap(k[i][g],k[j][g]);
24                     }//puts("Moxing");
25                     ans*=-1;
26                 }
27             }
28             ans=ans*k[j][j]%mod;
29         }
30         return (ans+mod)%mod;
31     }
32     struct main {
33         main() {
34             
35             scanf("%d%d",&n,&m);
36             for(int i=1; i<=n; i++) {
37                 scanf("%s",s[i]+1);
38                 for(int j=1;j<=m;j++){
39                     if(s[i][j]==‘.‘){
40                         idx[i][j]=++cnt;
41                     }
42                 }
43             }
44             for(int i=1; i<=n; i++) {
45                 for(int j=1; j<=m; j++) {
46                     if(!check(i,j)) continue ;
47                     if(check(i+1,j)) {
48                         d[idx[i][j]][idx[i][j]]++;
49                         d[idx[i+1][j]][idx[i+1][j]]++;
50                         a[idx[i][j]][idx[i+1][j]]=a[idx[i+1][j]][idx[i][j]]=1;
51                     }
52                     if(check(i,j+1)) {
53                         d[idx[i][j]][idx[i][j]]++;
54                         d[idx[i][j+1]][idx[i][j+1]]++;
55                         a[idx[i][j]][idx[i][j+1]]=a[idx[i][j+1]][idx[i][j]]=1;
56                     }
57                 }
58             }
59             cnt--;
60             for(int i=1; i<=cnt; i++) {
61                 for(int j=1; j<=cnt; j++) {
62                     k[i][j]=((d[i][j]-a[i][j])+mod)%mod;//,cout<<k[i][j]<<‘ ‘;
63                 }
64             }
65             printf("%lld\n",gauss());
66             exit(0);
67         }
68     } UniversalLove;
69 }
70 int main() {
71     Moxing::main();
72 }