BZOJ 4031: [HEOI 2015] 작은 Z 의 방.
방법: matrix - tree 로 정리 합 니 다.하나의 그림 에 대해 라 프 라 스 연산 자 c c [i] [j] = d [i] [j] - a [i] [j], d 는 도수 행렬 이 고 i = j 일 때 i 의 도수 이 며 그렇지 않 으 면 0 이 고 a 는 인접 행렬 이다.그리고 행렬 c 의 행렬식 을 구하 세 요.나의 방법 은 고 스 소원 이다. c 를 상 삼각형 으로 소 거 한 후에 대각선 의 곱셈 을 구 하 는 것 이다. 그러나 이 문 제 는 10 ^ 9 에 대해 모델 링 을 해 야 하기 때문에 소원 을 소 거 할 때 double 제 거 를 할 수 없고 끊임없이 뒤 척 이 며 제거 해 야 한다.Tips: 행렬식 계산 시 한 줄 에 1 을 곱 하고 배열 기록 을 엽 니 다.
#include
#include
#include
#include
using namespace std;
const int maxn=100+10;
const int md=1000000000;
int a[maxn][maxn],d[maxn][maxn],map[maxn][maxn],n,id[maxn][maxn],tot,m;
long long c[maxn][maxn];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
char ch[12];
void gauss(int n)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
c[i][j]=(c[i][j]+md)%md;
int f=1;
for(int i=1;i<=n;i++)
{
int j=i;
while(!c[j][i]&&j<=n) j++;
if(j==n+1)
{
puts("0");
return;
}
if(j!=i)
{
for(int k=1;k<=n;k++) swap(c[i][k],c[j][k]);
f*=-1;
}
for(int k=i+1;k<=n;k++)
{
while(c[k][i])
{
long long t=c[k][i]/c[i][i];
for(int l=i;l<=n;l++) c[k][l]=(c[k][l]-c[i][l]*t%md+md)%md;
if(!c[k][i]) break;
for(int l=i;l<=n;l++) swap(c[k][l],c[i][l]);
f*=-1;
}
}
}
long long res=1;
for(int i=1;i<=n;i++) res=(res*c[i][i])%md;
if(f<0) res=(md-res)%md;
printf("%lld
",res);
}
int main()
{
//freopen("4031.in","r",stdin);
//freopen("4031.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",&ch);
for(int j=0;jif(ch[j]=='.') map[i][j+1]=1;
else map[i][j+1]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
if(map[i][j]) id[i][j]=++tot;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(map[i][j])
{
for(int k=0;k<4;k++)
{
int nx=i+dx[k],ny=j+dy[k],u=id[i][j],v=id[nx][ny];
if(nx&&nx<=n&&ny&&ny<=m&&map[nx][ny])
{
a[u][v]=1;d[u][u]++;
}
}
}
for(int i=1;i<=tot;i++)
for(int j=1;j<=tot;j++)
c[i][j]=d[i][j]-a[i][j];
//cout<
gauss(tot-1);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.