QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#588379#9278. Linear Algebra Intensifieszjy0001WA 5ms19872kbC++171.8kb2024-09-25 10:09:052024-09-25 10:09:09

Judging History

你现在查看的是最新测评结果

  • [2024-09-25 10:09:09]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:19872kb
  • [2024-09-25 10:09:05]
  • 提交

answer

#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
typedef vector<int> Vec;
typedef vector<Vec> Mat;
const int N=5e5+5,Mod=998244353;
int n,m,An;
vector<int>G[N];
vector<pair<int,int>>E;
int fd[N],A[N],id[N],nxt[N];
inline int qpow(int x,int y,int z=1){
	for(;y;(y>>=1)&&(x=(LL)x*x%Mod))if(y&1)z=(LL)z*x%Mod;return z;
}
inline int Det(Mat A){
    const int n=A.size();int z=1;
    for(int i=0;i<n;++i)
        for(int j=i+1;j<n;++j){
            while(A[i][i]){
                const int v=A[j][i]/A[i][i];
				for(int k=i;k<n;++k)
					A[j][k]=(A[j][k]-1ll*v*A[i][k])%Mod;
				A[i].swap(A[j]),z=-z;
            }
            A[i].swap(A[j]),z=-z;
        }
    for(int i=0;i<n;++i)z=1ll*z*A[i][i]%Mod;
    return z<0?z+Mod:z;
}
inline int find(const int&x){
	return x==fd[x]?x:fd[x]=find(fd[x]);
}
inline void dfs(int u,int fa){
	int ch=0,r=0;
	for(auto v:G[u])if(v!=fa){
		dfs(v,u);
		if(nxt[v])++ch,r=nxt[v];
	}
	if(ch>1||id[u]){
		id[u]=1;
		for(auto v:G[u])if(v!=fa&&nxt[v])
			E.emplace_back(u,nxt[v]);
		nxt[u]=u;
	}
	else nxt[u]=r;
}
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m,++n;
	iota(fd+1,fd+n+1,1);
	for(int i=1;i<=m;++i){
		int u,v;cin>>u>>v,++v;
		if(find(u)!=find(v)){
			G[u].emplace_back(v);
			G[v].emplace_back(u);
			fd[find(u)]=find(v);
		}
		else{
			id[u]=id[v]=1;
			E.emplace_back(u,v);
		}
	}
	for(int i=1;i<=n;++i)if(find(i)!=find(1))return cout<<"0\n",0;
	if(E.empty())return cout<<"1\n",0;
	dfs(1,0);
	for(int i=1;i<=n;++i)id[i+1]+=id[i];
	Mat Q(id[n],Vec(id[n]));
	for(auto [u,v]:E)
		u=id[u]-1,v=id[v]-1,
		--Q[u][v],--Q[v][u],++Q[u][u],++Q[v][v];
	Q.pop_back();
	for(auto&i:Q)i.pop_back();
	cout<<Det(Q)<<'\n';
	return 0;
}
/*
*/

详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 19872kb

input:

3 4
1 2
2 3
1 2
3 3

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 18496kb

input:

1 1
1 1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 19480kb

input:

1 10
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1

output:

10

result:

ok 1 number(s): "10"

Test #4:

score: 0
Accepted
time: 2ms
memory: 18072kb

input:

2 1
1 2

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 4ms
memory: 18144kb

input:

2 2
1 2
1 1

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 19828kb

input:

2 3
1 1
2 2
1 2

output:

2

result:

wrong answer 1st numbers differ - expected: '3', found: '2'