7.13 模拟赛 T3

Description

Solution

令 $f_S,g_S$ 表示从 $1$ 和 $2$ 恰好到达点集 $S$ 的方案数，注意此方案只定 $S$ 内部的边。令 $s_S$ 表示点集 $S$ 内部的点。

考虑容斥，先令 $f_S=2^{s_S}$，表示内部随意定向，外部点指向 $S$ 。然后减去到达不了的个数。

考虑经典容斥（地震后的幻想乡？)，枚举包含 $1$ 的可以到达的点集 $S’$，然后钦定外部点内部随意，最外层都指向 $S’$，也就是减去 $f_{S’}\times2^{s_{S-S’}}$。

$g$ 同理。

后考虑算出答案。还是用容斥，令 $ans=2^m$。减去 $1$ 和 $2$ 到达的点不相交的数量。考虑枚举 $1$ 到达的点集 $S$，$2$ 到达的点集 $T$。注意此时 $S$ 相邻的点集 $h_S$ 和 $T$ 不能相交，不然交集的定向会与定义矛盾。而剩下情况都可以满足，乘上 $S,T$ 之外的点内部随意定向即可。

Code

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
const int mod=998244353;
int f[(1<<17)+5],g[(1<<17)+5],s[(1<<17)+5],h[(1<<17)+5];
int n,m,pw[505],ans;
struct yyy{
	int x,y;
}e[505];
inline void add(int &x,int y) {x=(x+y)%mod;}
vector<int>to[17];
signed main(void){
	freopen("silver.in","r",stdin);
  	freopen("silver.out","w",stdout);
	int i,j;
	read(n);read(m);
	for (pw[0]=1,i=1;i<=m;i++) pw[i]=pw[i-1]*2%mod;
	for (i=1;i<=m;i++) {
		read(e[i].x),read(e[i].y);
		e[i].x--;e[i].y--;
		to[e[i].x].push_back(e[i].y);
		to[e[i].y].push_back(e[i].x);
	}
	for (i=0;i<n;i++) {
		h[1<<i]=(1<<i);
		for (auto y:to[i]) h[1<<i]|=(1<<y);
	}
	int N=(1<<n);
	for (i=1;i<N;i++) {
		int tmp=__builtin_ctzll(i);
		h[i]=h[i^(1<<tmp)]|h[1<<tmp];
	}
	for (i=1;i<N;i++) {
		int tmp=__builtin_ctzll(i);
		s[i]+=s[i^(1<<tmp)];
		for (auto y:to[tmp]) if ((i>>y)&1) s[i]++;
	}
	
	for (i=1;i<N;i+=4) if (i&1) {
		f[i]=pw[s[i]];
		for (j=i&(i-1);j;j=(j-1)&i) if (j&1) add(f[i],mod-f[j]*pw[s[i^j]]%mod);
	}
	
	for (i=2;i<N;i+=4) if ((i>>1)&1) {
		g[i]=pw[s[i]];
		for (j=i&(i-1);j;j=(j-1)&i) if ((j>>1)&1) add(g[i],mod-g[j]*pw[s[i^j]]%mod);
	}
	
	for (i=1;i<N;i++) if (i&1){
		int tmp=(i^(N-1));
		for (j=tmp&(tmp-1);j;j=(j-1)&tmp) {
			int T=j;
			if ((T>>1)%2&&(h[i]&T)==0) {
				add(ans,f[i]*g[T]%mod*pw[s[(N-1)^i^T]]);
			}
		}
	}
	printf("%lld",(pw[m]-ans+mod)%mod);
	return 0;
}