T3 [ABC213G] Connectivity 2
题意：给定一张无向图 \(G\)，将其删去 \(0\) 条及以上的边构成一张新图，求对于所有点 \(k\in(1,n]\)，使 \(k\) 与 \(1\) 连通的新图的个数。
比较套路的一道状压 DP。尽管刚开始思考毫无头绪。
Step 1.
令 \(f_S\) 表示点集为 \(S\) 的连通子图的个数，\(g_S\) 为点集为 \(S\) 的子图的个数，则答案 \(\mathit{ans}_i\) 可以表示为
\[\mathit{ans}_i=\sum_{\text{path}(1,i)\subseteq S}f_S\times g_{\complement S} \]这部分复杂度是 \(O(2^nn)\) 的。
Step 2.
计算 \(g_S\)。这部分是简单的，求出满足两个端点 \(u,v\in S\) 的边 \((u,v)\) 的个数，记为 \(\mathit{cnt}\)，则
\[g_S=2^{\mathit{cnt}} \]这部分的复杂度是 \(O(2^nm)\)。
Step 3.
计算 \(f_S\)。正难则反，考虑容斥。$f_S=g_S-\text{点集为 \(S\) 的不连通子图的个数}$。
后面这部分又是一个很套路的计算方法：钦定一个点 \(u\in S\)，把不连通子图分为两部分：包含 \(u\) 的连通块、不包含 \(u\) 的其他部分。则有
\[f_S=g_S-\sum_{v\in T\subset S}f_T\times g_{\complement T} \]这部分需要枚举子集的子集，复杂度 \(O(3^n)\)。
综上，总复杂度为 \(O(3^n+2^nn+2^nm)\)。
坑点：
- 时刻注意状压的意义是从左到右还是从右到左。事实上，这道题与平常的状压不同，从左到右会方便很多。
- 在计算答案时所需要的 \(f_S\) 只需要包含 \(1\) 的点集，所以在计算 \(f_S\) 时只需要枚举 \(2^{n-1}\le S<2^n\) 的情况。所以我们上述的 “钦定一个点 \(u\in S\)” 也可直接钦定 \(1\)。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
#define int long long
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
if(sf^'#')putchar(sf);
}
using ll=long long;
constexpr int MOD=998244353;
int n,m;
int f[(1<<17)+5],g[(1<<17)+5];
int e[18][18];
int fac[17*17+5]={1};
void add(int&x,int y){
x=x+y>=MOD?x+y-MOD:x+y;
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n*n;++i)fac[i]=fac[i-1]*2%MOD;
for(int i=1,u,v;i<=m;++i){
u=read(),v=read();
e[u][v]=e[v][u]=1;
}
for(int s=0,cnt;s<1<<n;++s){
cnt=0;
for(int i=1;i<=n;++i)
if(s&(1<<(i-1)))
for(int j=i+1;j<=n;++j)
if(s&(1<<(j-1))&&e[n-i+1][n-j+1])
++cnt;
add(g[s],fac[cnt]);
}
for(int s=1<<(n-1),tmp;s<1<<n;++s){
tmp=0;
for(int t=s;t>=1<<(n-1);t=(t-1)&s)
if(t^s&&t&(1<<(n-1)))
add(tmp,(ll)f[t]*g[s^t]%MOD);
f[s]=(g[s]-tmp+MOD)%MOD;
}
for(int i=2,ans;i<=n;++i){
ans=0;
for(int s=1<<(n-1);s<1<<n;++s)
if(s&(1<<(n-i)))
add(ans,(ll)f[s]*g[((1<<n)-1)^s]%MOD);
write(ans);
}
return fw,0;
}