给一个无向图，求有多少个子图是基环树。
枚举环后缩点，再求生成树计数。
2^n枚举环上的点，dp预处理出每个集合的环的个数（默认以编号最小的点为起点），用f[i][s]表示环尾为i，点集为s。
【【hdu5304】生成树计数—基尔霍夫矩阵 DP】
#include
#include
#include
#include
#include
#define Rep(i, x, y) for (int i = x;
i <= y;
i ++)
#define Dwn(i, x, y) for (int i = x;
i >= y;
i --)
#define RepE(i, x) for(int i = pos[x];
i;
i = g[i].nex)
using namespace std;
typedef long long LL;
const int N = 18, mod = 998244353, S = (1 << 17) + 2;
int n, m, nx, d[N][N], c[N], l;
LL a[N][N], ans, f[N][S];
LL Pow(LL x, LL y) {
if (x < 0) x += mod;
LL z = 1;
while (y) {
if (y & 1) z = z * x % mod;
x = x * x % mod, y >>= 1;
}
return z;
}
LL Gauss() {
int fl = 1;
Rep(i, 1, l) {
Rep(j, i, l) if (a[j][i]) {
if (i != j) fl *= -1;
Rep(k, 1, l) swap(a[i][k], a[j][k]);
break ;
}
if (!a[i][i]) return 0;
LL tp = Pow(a[i][i], mod - 2);
Rep(j, i + 1, l) if (a[j][i]) {
LL z = a[j][i] * tp % mod;
Rep(k, 1, l) a[j][k] = (a[j][k] - (z * a[i][k] % mod) + mod) % mod;
}
}
LL s = fl;
Rep(i, 1, l) s = (s * a[i][i]) % mod;
return (s + mod) % mod;
}
int main()
{
while (scanf ("%d%d", &n, &m) != EOF) {
nx = 1 << n;
ans = 0;
memset(d, 0, sizeof(d));
Rep(i, 1, n) Rep(j, 0, nx) f[i][j] = 0;
Rep(i, 1, m) {
int x, y;
scanf ("%d%d", &x, &y);
d[x][y] = d[y][x] = 1;
}
Rep(i, 1, n) {
f[i][1 << i-1] = 1;
Rep(s, (1 << i-1), nx - 1) if ((((1 << i-1) - 1) & s) == 0){
Rep(j, i, n) if (f[j][s]) {
Rep(k, i + 1, n) if ((s & (1 << k-1)) == 0 && d[j][k]) {
(f[k][s + (1 << k-1)] += f[j][s]) %= mod;
}
}
}
}
Rep(s, 1, nx - 1) {
Rep(i, 1, n) Rep(j, 1, n) a[i][j] = 0;
int k;
LL sc = 0;
Rep(i, 0, n - 1) if ((1 << i) & s) { k = i + 1;
break ;
}
c[k] = l = 1;
Rep(i, k + 1, n) if ((1 << i-1) & s) {
(sc += f[i][s] * d[i][k]) %= mod;
c[i] = 1;
}
Rep(i, 1, n) if (!((1 << i-1) & s)) c[i] = ++ l;
if (n - l < 2) continue ;
Rep(i, 1, n) {
Rep(j, i + 1, n) if (d[i][j]) {
int x = c[i], y = c[j];
a[x][y] --, a[y][x] --, a[x][x] ++, a[y][y] ++;
}
}
l --;
(ans += (Gauss() * sc % mod) * Pow(2, mod - 2)) %= mod;
}
printf ("%I64d\n", ans);
} return 0;
} 推荐阅读
- topcoder|Topcoder SRM 661 Div1 Easy: MissingLCM
- 数学|【Topcoder SRM 641】BitToggler 期望 高斯消元
- 数学|【SRM 565 UnknownTree】计数 分类讨论