题目大意
给你一张 \(n\) 个点 \(m\) 条边的图，求有多少种删边方法使得删完后的图是一张联通二分图。
\(n\le 17,m\le\dfrac{n(n-1)}{2}\)
解题思路
状压dp，枚举点，然后联通二分图怎么计数呢？
将联通二分图拆成二分图和联通，联通在 前置芝士 里已经讲了，所以先解决二分图。
怎么计数二分图呢？将一个点集分成两部分，即左部点和右部点，然后两个点集之间随机连边即可，所以二分图个数
\(g_i=\sum\limits_{l\subset i}2^{\sum\limits_{e_j=\{u,v\}}{[u\in i\land v\in i]-[u\in l\land v\in l]-[u\in i\setminus l\land v\in i\setminus l]}}\)
再来算联通，和上一题一样，\(h_i=\sum\limits_{j\subset all\land i\in j}{f_jg_{all\setminus j}}\)
所以有 \(f_i=g_i-h_i\)
注意到左右部点可以互换，所以最后答案就是 \(\dfrac{f_{all}}{2}\)
细节
- 因为是在模意义下运算，所以除2要写成 \(\times 2^{p-2}\)。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 17, M = 200, p = 998244353;
int f[1 << N], g[1 << N], p2[M];
int n, m, u[M], v[M], ce[1 << N];
int lowbit(int x){return x & (-x);}
int cnte(int x)
{
int cnt = 0;
for(int i = 1; i <= m; i ++)
cnt += (x & (1 << u[i] - 1)) && (x & (1 << v[i] - 1));
return cnt;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i ++)
cin >> u[i] >> v[i];
p2[0] = 1;
for(int i = 0; i < (1 << n); i ++) ce[i] = cnte(i);
for(int i = 1; i <= m; i ++) p2[i] = p2[i - 1] * 2 % p;
for(int i = 0; i < (1 << n); i ++)
{
g[i] = 1;
for(int j = i; j; j = (j - 1) & i)
(g[i] += p2[ce[i] - ce[j] - ce[i ^ j]]) %= p;
}
for(int i = 0; i < (1 << n); i ++)
{
f[i] = g[i];
int k = lowbit(i);
for(int j = i - lowbit(i); j; j = (j - 1) & i)
if(j & k)
(f[i] -= f[j] * g[i ^ j]) %= p;
}
cout << (f[(1 << n) - 1] + p) % p * 499122177ll % p;
return 0;
}