AcWing 2926. 小Z的房间
原题链接
困难
作者:
我已经不想再做刺客了
,
2021-05-24 05:06:52
,
所有人可见
,
阅读 274
#include <iostream>
#include <cstring>
#include <algorithm>
#define A a
#define int long long
using namespace std;
const int mod=1e9;
char c[100][100];
int a[100][100];
int ans=1,m,n,mp[100][100];
void add(int x,int y){
a[x][y]--;
a[y][x]--;
a[x][x]++;
a[y][y]++;
}
signed main(){
cin>>m>>n;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++)cin>>c[i][j];
}
int cnt=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(c[i][j]=='.')mp[i][j]=++cnt;
}
}
//cout<<cnt<<endl;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(c[i][j]=='.'&&c[i+1][j]=='.')add(mp[i][j],mp[i+1][j]);
if(c[i][j]=='.'&&c[i][j+1]=='.')add(mp[i][j],mp[i][j+1]);
}
}
cnt--;
for(int i=1;i<cnt;i++){
for(int j=i+1;j<=cnt;j++){
while(A[j][i]){
int l=A[i][i]/A[j][i];
//这里不能直接取模,要先计算商
for(int k=1;k<=cnt;k++)
A[i][k]=(A[i][k]-A[j][k]*l%mod+mod)%mod;
for(int k=1;k<=cnt;k++) swap(A[i][k],A[j][k]);
ans*=-1;
//每次交换两行,将答案取相反数
}
}
}
for(int i=1;i<=cnt;i++) ans=(ans*A[i][i]%mod+mod)%mod;
cout<<ans;
}