https://www.luogu.com.cn/problem/AT_abc213_g
挺典但好题。
考虑钦定点集来解决问题，因为边集是不好状压的。又因为这个题的答案是某两个点联通，那么答案的表达式一定可以写成 \(ans=\sum\limits_{\{1,x\} \subseteq T} f(T)g(S/T)\)，因为考虑形成的图使得 \(1,x\) 联通，显然 \(1,x\) 在一个连通块内，考虑钦定这个连通块的点集 \(V\)，那么其余部分显然是任意的。考虑其是否不重不漏。对于一个图，\(x\) 所在连通块为 \(V\)，显然这个图会被钦定到且一定只会钦定到一次。
\(f(S)\) 为仅考虑点集 \(S\) 的点导出子图，让 \(S\) 成为一个连通块的子图数量。
\(g(S)\) 为仅考虑点集 \(S\) 的点导出子图，其所有的子图数。
那么 \(f(S)\) 往往是通过容斥解决，即求出 \(f'(S)\) 为 \(S\) 不连通的方案数，那么 \(f(S)=g(S)-f'(S)\)。
那么考虑 \(S\) 中的某一个点 \(v\)，所有不连通的子图均可以变为，钦定 \(v\) 这个点所在连通块 \(V,V\not=S\)，那么变为了 \(f(V)g(S-V)\)，不重不漏的分析可以参考答案的计算的分析。显然每个子图都会被钦定到，且又因为我们钦定的是 \(v\) 所在连通块，所以每个图会被唯一钦定到一次。
即 \(f'(S)=\sum_{v\in T,T\subseteq S,T\not =S} f(T)g(S-T)\)，枚举子集大力做即可。
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int mod=998244353;
vector<int>e[17];
bool vis[17];
int f[(1<<17)],g[(1<<17)],n,m;
int fpow(int x,int y) {
int res=1; x%=mod;
while(y) {
if(y&1) res=res*x%mod;
y>>=1; x=x*x%mod;
} return res;
}
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++) {
int x,y; cin>>x>>y;
--x; --y;
e[x].pb(y); e[y].pb(x);
}
for(int S=0;S<(1<<n);S++) {
for(int i=0;i<n;i++) {
vis[i]=((S>>i)&1);
}
int qwq=0;
for(int i=0;i<n;i++)
for(int j:e[i])
if(vis[i]&&vis[j]) ++qwq;
// cout<<S<<" "<<qwq<<'\n';
qwq/=2; g[S]=fpow(2,qwq);
}
f[0]=1;
for(int S=1;S<(1<<n);S++) {
int v=0;
for(int i=0;i<n;i++) {
if((S>>i)&1) {
v=i; break ;
}
}
int SS=(S^(1<<v));
for(int T=(SS-1)&SS;;T=(T-1)&SS) {
int TT=T^(1<<v);
f[S]=(f[S]+f[TT]*g[S^TT]%mod)%mod;
if(!T) break ;
}
f[S]=(g[S]-f[S]+mod)%mod;
}
for(int i=1;i<n;i++) {
int T=(1<<i)+1;
int SS=((1<<n)-1)^T;
int ans=0;
for(int S=SS;;S=(S-1)&SS) {
int TT=S^T;
ans=(ans+f[TT]*g[((1<<n)-1)^TT]%mod)%mod;
if(!S) break ;
}
ans=(ans%mod+mod)%mod;
cout<<ans<<'\n';
}
return 0;
}