QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#241795 | #5437. Graph Completing | arahato | WA | 1ms | 3852kb | C++14 | 1.9kb | 2023-11-06 17:35:03 | 2023-11-06 17:35:04 |
Judging History
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'