赛时想了很久，可能是比较久没做这样的经典状压枚举子集的 dp 题了。
赛时大样例输出是错的，调了 40min 对的代码没看出来哪里错，写个对拍拍不出来，结果是 cxr 题面里的模数写错了，最后改了数据……
-
正难则反，求反面的方案数，即【1,2能到达的点无交集】的方案数
-
设 \(f_S\) 表示从 \(1\) 出发能够到达 \(S\)，在 \(S\) 内部给边定向的方案数。
-
同时求个辅助数组 \(cnt_S\) 表示 \(S\) 集合内部边的数量。
-
转移方程：\(f_S=2^{cnt_S}- \sum\limits_{\{1\}\subset T\subseteq S}f_T\times 2^{cnt_{S\backslash T}}\)
-
同时求一下 \(2\) 出发的 dp 数组 \(g\)。
-
最后再枚举一次子集，就完事了。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=16,E=N*N,M=1<<N,mod=998244353;
int n,m,U,a[N][N];
int f[M],cnt[M],pw[E];
int main(){
cin>>n>>m,U=(1<<n)-1;
for(int i=pw[0]=1;i<=m;i++)pw[i]=pw[i-1]*2%mod;
for(int u,v;m--;){
cin>>u>>v,u--,v--;
a[u][v]=a[v][u]=1;
}
for(int S=1;S<=U;S++){
cnt[S]=cnt[S^(S&-S)];
int i=__builtin_ctz(S);
for(int j=i+1;j<n;j++)if(S>>j&1)cnt[S]+=a[i][j];
}
f[1]=f[2]=1;
for(int S=5;S<=U;S+=4){
f[S]=pw[cnt[S]];
for(int T=S&(S-1);T;--T&=S)if(T&1)
f[S]=(f[S]+1ll*(mod-f[T])*pw[cnt[S^T]])%mod;
}
for(int S=6;S<=U;S+=4){
f[S]=pw[cnt[S]];
for(int T=S&(S-1);T;--T&=S)if(T&2)
f[S]=(f[S]+1ll*(mod-f[T])*pw[cnt[S^T]])%mod;
}
int ans=0;
for(int S=1;S<=U;S+=4){
int T=U^S;
for(int R=T;R;--R&=T)if(R&2)
if(cnt[S|R]==cnt[S]+cnt[R])
ans=(ans+1ll*f[S]*f[R]%mod*pw[cnt[U^S^R]])%mod;
}
cout<<(pw[cnt[U]]-ans+mod)%mod;
return 0;
}