QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#766957 | #5437. Graph Completing | SGColin | WA | 6ms | 54132kb | C++20 | 2.0kb | 2024-11-20 19:26:00 | 2024-11-20 19:26:09 |
Judging History
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'