QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#766957#5437. Graph CompletingSGColinWA 6ms54132kbC++202.0kb2024-11-20 19:26:002024-11-20 19:26:09

Judging History

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

  • [2024-11-20 19:26:09]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:54132kb
  • [2024-11-20 19:26:00]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

constexpr int N = 5007;
constexpr int M = 12500007;
constexpr int mod = 998244353;

vector<int> E[N], e[N];

int dfntot, dfn[N], low[N], bel[N], bcctot;

void tarjan(int u, int fa) {
	static stack<int> s;
	s.push(u);
	low[u] = dfn[u] = ++dfntot;
	for (auto v : E[u]) 
		if (!dfn[v]) {
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] > dfn[u]) {
				++bcctot;
				do {
					bel[s.top()] = bcctot; s.pop();
				} while (!bel[v]);
			}
		} else if (v != fa) low[u] = min(low[u], dfn[v]);
}

int sz[N], num[N], pw[M], f[N][N], g[N];

inline int mo(int x) {return x >= mod ? x - mod : x;}

void dfs(int u, int fa) {
	f[u][sz[u]] = 1;
	for (auto v : e[u]) if (v != fa) {
		dfs(v, u);
		rep(j1, 1, sz[u]) rep(j2, 1, sz[v]) {
			g[j1 + j2] = (g[j1 + j2] + 1ll * f[u][j1] * f[v][j2] % mod * pw[j1 * j2 - 1]) % mod;
			g[j1] = mo(g[j1] + mod - 1ll * f[u][j1] * f[v][j2] % mod);
 		}
 		sz[u] += sz[v];
 		rep(j, 1, sz[u]) f[u][j] = g[j], g[j] = 0;
	}
}

int main() {
	pw[0] = 1;
	rep(i, 1, M - 1) pw[i] = mo(pw[i - 1] << 1);
	int n = rd(), m = rd();
	rep(i, 1, m) {
		int u = rd(), v = rd();
		E[u].eb(v); E[v].eb(u);
	}
	tarjan(1, 1);
	rep(u, 1, n) {
		++sz[bel[u]];
		for (auto v : E[u]) {
			if (bel[u] == bel[v]) ++num[bel[u]];
			else e[bel[u]].eb(bel[v]);
		}
	}
	int inner = 0, ans = pw[n * (n - 1) / 2 - m];
	if (bcctot == 0) {printf("%d\n", ans); return 0;}
	rep(i, 0, bcctot) inner += (sz[i] * (sz[i] - 1) - num[i]) / 2;
	dfs(0, 0);
	rep(i, 1, n) ans = mo(ans + f[0][i]);
	printf("%lld\n", 1ll * ans * pw[inner] % mod);
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 6ms
memory: 54132kb

input:

3 2
1 2
2 3

output:

3

result:

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