QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#241795#5437. Graph CompletingarahatoWA 1ms3852kbC++141.9kb2023-11-06 17:35:032023-11-06 17:35:04

Judging History

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

  • [2023-11-06 17:35:04]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3852kb
  • [2023-11-06 17:35:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N=5005,mod=998244353;
int dfn[N],low[N],num,n,lim,cn,st[N],dcc[N],m,hbee[N],bas[N],sz[N],pw[N],ppw[N],f[N][N];
vector<int> g[N],G[N];

void tarjan(int x,int fa){
	dfn[x]=low[x]=++num;
	st[++lim]=x;
	for(int y:G[x]){
		if(y==fa) continue;
		if(!dfn[y]){
			tarjan(y,x);
			low[x]=min(low[x],low[y]);
		}
		else{
			if(!dcc[y]) low[x]=min(low[x],dfn[y]);
		}
	}
	if(low[x]==dfn[x]){
		int top;
		cn++;
		for(;;){
			top=st[lim--];
			dcc[top]=cn;
			sz[cn]++;
			if(top==x) return ;
		}
	}
}

void init(int n){
	pw[0]=1;for(int i=1;i<=n;i++) pw[i]=2ll*pw[i-1]%mod;
	ppw[0]=1;for(int i=1;i<=n;i++) ppw[i]=1ll*pw[n]*ppw[i-1]%mod;
}

int expow(int p){
	return 1ll*pw[p%n]*ppw[p/n]%mod;
}

int C2(int x){
	return x*(x-1)/2;
}

void dfs(int x,int fa){
	f[x][sz[x]]=expow(C2(sz[x])-hbee[x]);
	for(int y:g[x]) if(y^fa){
		dfs(y,x);
		vector<int> _f(sz[x]+sz[y]+1,0);
		for(int i=bas[x];i<=sz[x];i++) _f[i]=f[x][i];
		for(int i=bas[x];i<=sz[x];i++) if(f[x][i])
			for(int j=bas[y];j<=sz[y];j++) if(f[y][j]){
				_f[i+j]=(_f[i+j]+1ll*f[x][i]*f[y][j]%mod*(expow(i*j-1)-1)%mod)%mod;
				_f[i]=(_f[i]-1ll*f[x][i]*f[y][j]%mod+mod)%mod;
			}
		for(int i=bas[x];i<=sz[x]+sz[y];i++) f[x][i]=_f[i];
//		if(x==1) for(int i=1;i<=n;i++) cout<<f[x][i]<<" ";
//		if(x==1) cout<<endl;
		sz[x]+=sz[y];
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	init(n);
	for(int i=1,x,y;i<=m;i++){
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i);
	for(int x=1;x<=n;x++) for(int y:G[x]) if(dcc[x]^dcc[y]){
		g[dcc[x]].push_back(dcc[y]);
	}
	else hbee[dcc[x]]++;
	for(int i=1;i<=cn;i++) hbee[i]>>=1,bas[i]=sz[i];
	dfs(1,0);
//	for(int i=1;i<=n;i++,cout<<endl) for(int j=1;j<=n;j++) cout<<f[i][j]<<" ";
	int ans=0;
	for(int i=bas[1];i<=n;i++) ans=(ans+f[1][i])%mod;
	cout<<ans;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3696kb

input:

3 2
1 2
2 3

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3804kb

input:

4 4
1 2
2 3
3 4
4 1

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

2 1
1 2

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

3 3
1 2
2 3
3 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 3828kb

input:

4 3
1 2
2 3
3 4

output:

0

result:

wrong answer 1st numbers differ - expected: '5', found: '0'