( ext{G - Connectivity 2})

解法

设 (f(s)) 是点集为 (s) 形成 全连通块 的个数，(g(s)) 是点集为 (s) 形成连通块的个数，(k) 的答案是 (h(k))。

[h(k)=sum_{{1,k}subseteq ssubseteq 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(mcdot 2^n)) 内算出所有的 (g)。

关于 (f)，有：

[f(s)=g(s)-sum_{tsubsetneq 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],'
');
	return 0;
}