\(\text{G - Connectivity 2}\)
解法
设 \(f(s)\) 是点集为 \(s\) 形成 全连通块 的个数，\(g(s)\) 是点集为 \(s\) 形成连通块的个数，\(k\) 的答案是 \(h(k)\)。
\[h(k)=\sum_{\{1,k\}\subseteq s\subseteq U} f(s)\cdot g(U-s) \]对于每个 \(k\) 都能在 \(\mathcal O(2^n)\) 内计算。
如何求解 \(f,g\)？\(g\) 比较好算，假设 \(s\) 内包含可选边集为 \(e(s)\)，那么 \(g(s)=2^{|e(s)|}\)。可以在 \(\mathcal O(m\cdot 2^n)\) 内算出所有的 \(g\)。
关于 \(f\)，有：
\[f(s)=g(s)-\sum_{t\subsetneq s}f(t)\cdot g(s-t) \]这个转移是 \(\mathcal O(3^n)\) 的。
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' or s<'0')
f|=(s=='-');
while(s>='0' and s<='9')
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar('-'),write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
const int mod=998244353,maxn=(1<<17);
int n,f[maxn],g[maxn],e[20][20],m,U;
int ans[20];
int qkpow(int x,int y) {
int r=1;
while(y) {
if(y&1) r=1ll*r*x%mod;
x=1ll*x*x%mod; y>>=1;
}
return r;
}
int main() {
n=read(9),m=read(9);
int u,v;
for(int i=1;i<=m;++i) {
u=read(9),v=read(9);
e[u][v]=e[v][u]=1;
}
U=(1<<n);
for(int i=0;i<U;++i) {
int e_cnt=0;
for(int j=1;j<=n;++j)
if((i>>j-1)&1)
for(int k=j+1;k<=n;++k)
if(((i>>k-1)&1) and e[j][k])
++e_cnt;
g[i]=qkpow(2,e_cnt);
}
for(int i=0;i<U;++i) {
if(!(i&1)) continue;
f[i]=g[i];
for(int j=(i-1)&i;j;j=(j-1)&i) {
if(!(j&1)) continue;
f[i]=(f[i]-1ll*f[j]*g[i^j]%mod+mod)%mod;
}
int tmp=1ll*f[i]*g[(U-1)^i]%mod;
for(int j=2;j<=n;++j)
if((i>>j-1)&1)
ans[j]=(ans[j]+tmp)%mod;
}
for(int i=2;i<=n;++i)
print(ans[i],'\n');
return 0;
}