Submission #43458607

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 17,mod = 998244353;

void add(ll& x, ll y) { x = (x + y >= mod) ? (x+y-mod) : (x+y); }
void sub(ll& x, ll y) { x = (x >= y) ? (x-y) : (x-y+mod); }
ll addv(ll x, ll y) { return (x + y >= mod) ? (x+y-mod) : (x+y); }
ll subv(ll x, ll y) { return (x >= y) ? (x-y) : (x-y+mod); }
//

ll P(ll x){
	return odd(x) ? (mod-1) : (1);
}

int n,m,G[MAXN][MAXN];

ll dp[1<<MAXN],cnt[1<<MAXN];

struct DSU{
	int fa[MAXN];
	void init(){
		iota(fa,fa+n,0);
	}
	int find(int x){
		return (fa[x] == x) ? (x) : (fa[x] = find(fa[x]));
	}
	void merge(int x,int y){
		fa[find(x)] = find(y);
	}
}dsu;

int main(){
	cin>>n>>m;

	rep(i,1,m){
		int u,v;cin>>u>>v;
		u--;v--;
		G[u][v] = G[v][u] = 1;
	}

	rep(mask,1,(1<<n)-1){
		dsu.init();
		rep(u,0,n-1)rep(v,u+1,n-1)if((mask>>u&1) && (mask>>v&1) && G[u][v]){
			dsu.merge(u,v);
		}
		rep(u,0,n-1)if((mask>>u&1) && dsu.find(u) == u)cnt[mask]++;
	}

	dp[0] = 1;

	rep(S,0,(1<<n)-1){
		int U = ((1<<n)-1) ^ S;
		for(int T = U;T;T = (T-1)&U){
			add(dp[S^T],1ll*dp[S]*P(cnt[T]-1)%mod);
		}
	}

	cout<<dp[(1<<n)-1]<<endl;

    return 0;
}

Submission Info

Judge Result